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

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

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

一定要以正确的方式编写生成子集的代码,否则您会多次生成相同的子集:为了避免内存化,由于映射查找和引入内存开销,内存化可能会很耗时,您可以以这种方式生成子集:

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());
    }
}

你可以递归地构造你的集合,从空集开始,尝试添加更多元素,如果其中一个子集(以及它的所有超集)不符合条件,就放弃递归执行。这里有一些伪代码,假设一个集合s的条件满足您想要列出的子集。为了方便起见,假设S的元素可以被索引为x(0)、x(1)、x。..

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子集不能包含在符合条件的子集中。

为了 在1- n ),那么您最终将枚举所有子集。

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

n -1,当位i为1时,选择元素i作为子集。

我为一个生成课程表的算法做了类似的事情。我们的课程表有两个元素——一个是添加到课程表中的课程列表,另一个是可添加的课程列表。

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)

修改它以解决你的问题应该很容易。

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)

我认为在最坏的情况下,你仍然需要生成所有子集并计算每个子集的总和,以确定它是否合格。渐近地,它是子集生成过程的成本。

//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);