I'm trying to write an algorithm that generates a list of an a size of lists where the union of any b amount of lists contains the set of numbers that appear in all lists. Also, no b - 1 amount of lists should contain the set of numbers that appear in all lists...
a can be between 1-9 and b can be between 0-9.
Example:
a = 3
b = 2
answer = [[0,1],[0,2],[1,2]]
I need three lists where the union of any 2 lists contains [0,1,2].
What I've done so far is write two functions, one checks whether a list of lists meets the criteria and returns a Boolean, the other generates combnations until the criteria is met (very inefficient, only works when b < 3).
from itertools import combinations
# Checks if an answer is successful
def check(answer, b):
# get set of total keys
answer_set = []
answer_set.extend([i for l in answer for i in l])
answer_set = set(answer_set)
# Check if all combinations of b size hold
for target in combinations(answer, b):
test = set([i for l in target for i in l])
if not answer_set.issubset(test):
return False
# Check if it doesn't hold for b - 1
for fail in combinations(answer, b - 1):
test = set([i for l in fail for i in l])
if answer_set.issubset(test):
return False
# Return True if all tests were passed
return True
# Brute force all combinations
def brute(a, b, answer=1):
# Establish set of numbers to try
test_set = set(range(answer))
# Test if set of numbers contains a passing answer
for attempt in range(10):
test_set.add(len(test_set))
set_combo = combinations(test_set, attempt)
for combo in combinations(set_combo, a):
if check(combo, b):
return combo
return brute(a, b, answer + 1)
If I typed everything in correctly, we should have code that answers my example above (albeit I believe it returns a tuple of tuples, but that isn't as important for now). Note: there are special cases that my brute force doesn't solve, like when a == b.
Obviously, the brute force isn't going to work on larger sized because the amount of possible combinations becomes insane to deal with. I need a new approach...
My thoughts moving forward would be to identify a special relationship between a and b, such that I can calculate the number of possible combinations whose union is the set of numbers which appear in all sets. Any information I can glean from a and b to get the size of lists and the possible number values of each item would be my next guess.
Anyway, any help is appreciated.
EDIT: Union, not intersection.
