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

Question

假设我有一个已经排好序的元素列表，我想生成所有满足某个条件的子集。这个条件是，如果一个给定的集合不满足这个条件，那么它的任何更大的子集也不会满足这个条件，而所有只有一个元素的集合都满足这个条件。

举个例子，假设我有一个包含所有小于100的正整数的列表，我想找出那些和小于130的子集，比如：(100,29)、(0,1,40)、(0)等等。

我该怎么做呢（最好是用Python）？

谢谢！:)

Answer 1

我之前做过一个类似的课程安排生成算法。我们的课程安排类有两个部分：一个是已经添加到安排中的课程列表，另一个是可以添加的课程列表。

伪代码：

queue.add(new schedule(null, available_courses))
while( queue is not empty )
    sched = queue.next()
    foreach class in sched.available_courses
        temp_sched = sched.copy()
        temp_sched.add(class)
        if(temp_sched.is_valid())
            results.add(temp_sched)
            queue.add(temp_sched)

这个想法是从一个空的课程安排开始，再加上可用课程的列表，然后在树形结构中寻找有效的安排（有效的意思是符合用户给出的要求，没有时间冲突等等）。如果一个安排是无效的，就把它丢掉——我们不能通过添加课程来让一个无效的安排变得有效（也就是修剪树形结构）。

修改这个方法来解决你的问题应该很简单。

Answer 2

你可以通过递归的方式来构建你的集合，首先从一个空集合开始，然后尝试添加更多的元素。如果某个子集（以及它的所有超集）不符合条件，就放弃这个递归的执行。下面是一些伪代码，假设有一个集合 S，你想列出它符合条件的子集。为了方便起见，假设 S 的元素可以用 x(0)、x(1)、x(2) 等来索引。

EnumerateQualifyingSets(Set T)
{
    foreach (x in S with an index larger than the index of any element in T)
    {
            U = T union {x}

            if (U satisfies condition)
            {
                print U
                EnumerateQualifyingSets(U)
            }
    }
}

第一次调用时，T 是空集合。然后，所有符合条件的 S 的子集都会被打印出来。这种方法的关键在于，如果 S 的某个子集不符合条件，那么它就不能包含在符合条件的子集中。

Answer 3

你可以使用一种叫做“分支限界”的方法来生成所有的子集。简单来说，就是逐步生成子集，每次都在已有的子集基础上增加新的元素。这里有个小技巧，如果某个条件不满足，就不再继续往下探索这个分支，就像在树上走路一样，遇到不合适的路就不走了。

如果你想让这个方法适用于不同的条件，我觉得这是最好的策略。

记得要正确地写出生成子集的代码，否则你可能会重复生成相同的子集。为了避免这种重复，我们可以用一种方法来生成子集，这样就不需要使用记忆化（这会因为查找而耗时，并且占用内存）。你可以这样生成子集：

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 的第一个元素，而第二次调用（如果没有违反剪枝条件）生成的子集则包含这个元素。因此，第一次和第二次生成的子集之间没有交集。