一种生成满足特定条件的集合的子集的算法

Question

假设我有一个元素的排序列表，我想生成满足某个条件的所有子集，这样如果给定的集合不满足条件，那么更大的子集也不会满足它，并且一个元素的所有集合都满足它。

例如，给定一个包含所有小于 100 的正整数的列表，确定总和小于 130 的子集：(100,29) (0,1,40)、(0) 等...

我该怎么做（最好是在 Python 中）？

谢谢！:)

Answer 1

您可以使用分支定界技术生成所有子集：您可以以增量方式生成所有子集（生成已经确定的子集的超集），使用作为修剪条件“不探索树的这个分支，如果root 不满足约束”。

如果你想对约束通用，我认为这是最好的策略。

确保以正确的方式编写生成子集的代码，否则您会多次生成相同的子集：为了避免记忆化，由于地图查找和引入内存开销，这可能会很耗时，您可以生成子集以这种方式：

GetAllSubsets(List objects) {
    List generated = {};
    GetAllSubsets(generated, [], objects);
    return generated;
}

GetAllSubsets(List subsetGenerated, List objectFixed, List objectsToFix) {
    GetAllSubsets(subsetGenerated, objectFixed, objectsToFix.sublist(1, objectsToFix.length());
    if (satisfy(toCheck = objectsFixed.add(objectsToFix.get(0)))) {
        subsetGenerated.add(toCheck);
        GetAllSubsets(subsetGenerated, toCheck, objectsToFix.sublist(1, objectsToFix.length());
    }
}

实际上，第一次调用 GetAllSubsets 添加的子集没有 objectsToFix 的第一个元素，其中第二次调用添加的子集（如果不违反修剪条件）具有该元素，因此两者的交集生成的子集集为空。