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

Question

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

例如，给定一个所有小于100的正整数的列表，确定其和小于130的子集:(100,29) (0,1,40), (0), etc...

我该怎么做(最好使用 Python)？

谢谢! :)

Answer 1

您可以使用 Branch-and-bound 生成所有子集技术:您可以以增量方式生成所有子集(生成已经确定的子集的超集)，使用修剪条件“如果根不满足约束，则不探索树的这个分支”。

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

一定要以正确的方式编写生成子集的代码，否则你会生成很多次相同的子集:为了避免记忆化，这可能会因 map 查找而耗时并引入内存开销，你可以以这种方式生成子集:

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 的第一个元素，而第二次调用(如果不违反修剪条件)添加的子集有那个元素，所以交集生成的两组子集中的一个为空。