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

Question

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

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

我怎样才能做到这一点（最好是用Python）？

谢谢！:)

Answer 1

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

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

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

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 的第一个元素，而第二次调用添加的子集（如果不违反剪枝条件）具有该元素，因此两者的交集生成的子集集为空。

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

有一定的方法来做到这一点，但除非你能以某种约束条件，这将需要O（2 ^ n）的步骤。如果考虑，例如其中所有子集将被选择在1-100的条件（例如，<Σ I 的 I 在1- 名词），那么你最终会枚举所有的子集。

您会看

for i in the powerset of {1-n}
    if cond(i)
       note that set

可以通过简单地生成所有二进制数从0至S得到设定的幂名词的-1，并选择元素i为所述子集时的位i为1。

Answer 4

我已经做了课表生成算法类似的东西。我们的时间表类有2种元素 - 的添加到计划课程列表，并且可添加的课程列表

伪代码：

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 5

下面是akappa的回答的一个具体的例子，使用一个递归函数以生成所述子集：

def restofsubsets(goodsubset, remainingels, condition):
    answers = []
    for j in range(len(remainingels)):
        nextsubset = goodsubset + remainingels[j:j+1]
        if condition(nextsubset):
            answers.append(nextsubset)
            answers += restofsubsets(nextsubset, remainingels[j+1:], condition)
    return answers

 #runs slowly
 easieranswer = restofsubsets([], range(101), lambda l:sum(l)<40)

 #runs much faster due to eliminating big numbers first
 fasteranswer = restofsubsets([], range(100,-1,-1), lambda l:sum(l)<40)

 #runs extremely slow even with big-numbers-first strategy
 finalanswer = restofsubsets([], range(100,-1,-1), lambda l:sum(l)<130)

Answer 6

我认为在最坏的情况下，你仍然有生成所有的子集，并计算出各组的总和，以确定它是否是合格与否。渐近，它是子集生成过程的成本。

以下是我在javascript实施了同样的想法的方法。

//this is to generate an array to test
var numbers = (function(start, end){
    var result = [],
        i =  start; 
    for(; i <= end; i++){
        result.push(i);
    }
    return result; 
})(1, 12);

//this is the qualifying function to determine if the generated array is qualified
var fn = (function(maxSum){
    return function(set){
        var sum = 0;
        for(var i = 0 ; i< set.length; i++){
            sum += set[i];
            if( sum > maxSum ){
                return false;
            }
        }
        return true;
    }
})(30);

//main function
(function(input, qualifyingFn){
    var result, mask, total = Math.pow(2, input.length);
    for(mask = 0; mask < total; mask++){

        result = [];
        sum = 0;

        i = input.length - 1; 
        do{
            if( (mask & (1 << i)) !== 0){
                result.push(input[i]);
                sum += input[i];
                if( sum > 30 ){
                    break;
                }
            }
        }while(i--);
        if( qualifyingFn(result) ){
            console.log(JSON.stringify(result));
        }
    }

})(numbers, fn);