1

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

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

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

谢谢！:)

4

6 回答 6

5

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

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

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

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

于 2009-06-01T18:34:04.747 回答
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 子集不能包含在满足条件的子集中。

于 2009-06-01T18:55:35.720 回答
1

当然有办法做到这一点，但除非你能以某种方式限制条件，否则它将采取 O(2^n) 步骤。例如，如果您考虑在 1-100 上选择所有子集的条件（例如，< Σ i for i in 1- n），那么您最终将枚举所有子集。

你会看着

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

您可以通过简单地生成从 0 到 s n -1 的所有二进制数，并在位 i 为 1 时为子集选择元素 i 来获得集合的幂集。

于 2009-06-01T18:20:22.883 回答
1

我为课程表生成算法做了类似的事情。我们的日程安排类有 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)

这个想法是从一个空的时间表和可用课程的列表开始，然后在树中搜索有效的时间表（有效的含义符合用户给出的要求，没有时间冲突等）。如果一个时间表无效，它就会被丢弃——我们不能通过添加类（即修剪树）使无效的时间表有效。

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

于 2009-06-01T19:13:33.593 回答
1

这是 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)
于 2009-06-01T19:26:26.453 回答
0

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

以下是我在 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);
于 2013-08-14T05:37:54.640 回答