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

Question

假设我给出了排序的元素列表，并且我想生成满足某些条件的所有子集，以便如果给定的集合不满足条件，则更大的子集也不会满足它，并且所有的一组元素都满足它。例如，给定所有小于100的正整数列表，确定总和小于130的子集：（100,29）（0,1,40），（0）等...

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

谢谢！ :)

Answer 1

您可以使用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()); 
    } 
} 

事实上，通过GetAllSubsets的第一次调用添加的子集不具有objectsToFix，其中所述子集由所述第二呼叫添加的第一个元素（如果修剪条件没有违反）具有该元素，因此生成的两组子集的交集是空的。

Answer 2

确实有办法做到这一点，但除非你能够以某种方式限制条件，否则将需要O（2^n）个步骤。如果你考虑，例如，所有的子集将选择在1-100的条件（例如，< Σ 我为我在1 ñ），那么你最终会枚举所有的子集。

你会看

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

您可以通过简单地生成所有二进制数从0至S ñ -1，并选择元素为我当位的子集获得设定的幂我是1.

Answer 3

您可以递归地构造您的集合，从空集合开始并尝试添加更多元素，如果其中一个子集（以及它的所有超集）中的一个未能满足条件，则放弃递归执行线。这里有一些伪代码，假设一个集合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 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);