Skip to content

Instantly share code, notes, and snippets.

@Althorion
Created December 16, 2018 14:07
Show Gist options
  • Save Althorion/5d3180b2f9453b911e9c36b006191017 to your computer and use it in GitHub Desktop.
Save Althorion/5d3180b2f9453b911e9c36b006191017 to your computer and use it in GitHub Desktop.
from typing import List
def generate_set(half_size: int) -> List[str]:
oranges: List[str] = [f"B{i + 1}" for i in range(half_size)]
blues: List[str] = [f"O{i + 1}" for i in range(half_size)]
return oranges + blues
def partition(collection):
# "borrowed" from https://stackoverflow.com/questions/19368375/set-partitions-in-python
if len(collection) == 1:
yield [collection]
return
first = collection[0]
for smaller in partition(collection[1:]):
# insert `first` in each of the subpartition's subsets
for n, subset in enumerate(smaller):
yield smaller[:n] + [[first] + subset] + smaller[n + 1:]
# put `first` in its own subset
yield [[first]] + smaller
def is_partition_good(partition: List[List[str]]) -> bool:
def is_subset_good(subset: List[str]) -> bool:
if len(subset) < 2:
return False
first_letters: List[str] = [word[0] for word in subset]
return any(map(lambda x: x == 'B', first_letters))
for subset in partition:
if not is_subset_good(subset):
return False
return True
if __name__ == "__main__":
for x in range(1, 6):
print(f"{x}:\t{len(list(filter(is_partition_good, list(partition(generate_set(x))))))}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment