my apologies if this was answered somewhere, I tried searching but I do not know if this kind of problem has a specific name, so nothing came up in my search...
I have a list of objects, and each of these objects can either be accepted or rejected. Every combination is assigned a value, while some combinations are not valid. (So for example we have 4 objects, and objects 1 and 2 don't go together, then every combination that has objects 1 and 2 as accepted is invalid.) It is not known beforehand which objects don't go together and it is not possible to find the invalid ones just by looking at pairs. (For example it is possible that objects 1, 2 are valid together, objects 2,3 are valid, objects 1,3 are valid, but 1,2,3 are invalid.) I modeled this as lists of 0 and 1, so now I want to traverse these lists to find the one with the maximum value in an efficient way.
My idea was to traverse the lists like a tree by starting at all zeros and then in each step flipping a zero to a one, so for example for 3 objects this gives the tree
000
/ | \
100 010 001
/ \ / \ / \
110 101 110 011 101 011
\ \ \ / / /
111
which is actually worse than just listing all 2^n options since there are duplicates, but at each node I could stop if I discovered that it is invalid. Saving the invalid combinations of ones and keeping a list of all already visited nodes I could make sure that I don't revisit already checked nodes. (But I would still have to check those if they were already visited)
Is there any better way to do this?
You can try to build tree of variants (at most 2^n options, as you noticed), but cut unappropriate branches as early as possible.
In example below I've set two binary masks - no 1,2,3 together and no 2,4 together
def buildtree(x, maxsize, level, masks):
if level == maxsize:
print("{0:b}".format(x).zfill(maxsize))
else:
buildtree(x, maxsize, level + 1, masks)
t = x | (1 << level)
good = True
for m in masks:
if (t & m) == m:
good = False
break
if good:
buildtree(t, maxsize, level + 1, masks)
buildtree(0, 4, 0, [7, 10])
0000
1000
0100
1100
0010
0110
0001
1001
0101
1101
0011
Is is possible also to remove some masks but code will be more complicated