遍历 0, 1 的列表

Question

很抱歉，如果有人在某个地方回答了这个问题，我尝试搜索，但我不知道这种问题是否有特定的名称，所以我的搜索没有任何结果...

我有一个对象列表，其中每个对象都可以接受或拒绝。每个组合都分配了一个值，而某些组合无效。（例如，我们有 4 个对象，对象 1 和对象 2 不在一起，那么每个接受对象 1 和 2 的组合都是无效的。）事先不知道哪些对象不在一起，它是不可能仅仅通过查看对来找到无效的。（例如，对象 1、2 可能一起有效，对象 2,3 有效，对象 1,3 有效，但 1,2,3 无效。）我将其建模为 0 和 1 的列表，所以现在我想遍历这些列表，以一种有效的方式找到具有最大值的列表。

我的想法是通过从所有零开始然后在每个步骤中将 0 翻转为 1 来像树一样遍历列表，因此例如对于 3 个对象这给出了树

                000
            /    |    \
        100     010     001
        / \     / \     / \
      110 101 110 011 101 011
        \  \   \   /   /   /
                111

这实际上比仅列出所有 2^n 个选项更糟糕，因为存在重复，但如果我发现它无效，我可以在每个节点停止。保存无效的组合并保留所有已访问节点的列表，我可以确保我不会重新访问已检查的节点。（但如果他们已经访问过，我仍然需要检查它们）

有什么更好的方法吗？

Answer 1

您可以尝试构建变体树（最多 2^n 个选项，如您所见），但应尽早剪掉不合适的分支。

在下面的示例中，我设置了两个二进制掩码 - 没有 1,2,3 在一起，也没有 2,4 在一起

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

也可以删除一些掩码，但代码会更复杂

遍历 0, 1 的列表

Traversing lists of 0, 1 with constraint

algorithm

list

maximization