生成滿足條件的集合的子集的算法

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