証明書条件を満たすセットのサブセットを生成するアルゴリズム

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の最初の呼び出しによって追加されたサブセットは第2の呼によってサブセットを加えobjectsToFixの最初の要素を持たない（剪定状態であれば違反していない）にはその要素があるため、生成された2つの部分集合の共通部分は空です。

Answer 2

確かにそれを行う方法はありますが、何らかの形で条件を制約できなければ、O（2^n）ステップを取ることになります。あなたが考える場合は、例えば、すべてのサブセットが選択される1-100の条件（例えば、1- nはで私ため< Σ 私）は、その後、あなたはすべてのサブセットを列挙することになります。

あなたは、あなたがたときに少し単に私がサブセットに対して0からののn -1にすべてのバイナリ番号を生成し、その要素を選択して設定の冪を得ることができます

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

を見ていると思いますiは1です。

Answer 3

空集合で始まり、要素を追加しようとすると、再帰的に集合を構築することができ、部分集合の1つ（したがってそのすべてのスーパーセット）が条件を満たすことができない場合、再帰的な実行行を断念します。ここではいくつかの擬似コードがあります。条件付きのサブセットをリストしたい集合Sを仮定します。便宜のために、（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) 
      } 
    } 
} 

Sの要素はXとしてインデックス付けすることができると仮定最初の呼び出しが空集合として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) 

アイデアは、空のスケジュールと利用可能なクラスのリストを開始するには、有効なスケジュールのために木を下に検索する（有効な意味は、ユーザによって与えられた要件に適合し、doesnのです時間の紛争などがあります）。スケジュールが無効であれば、それは破棄されます。クラスを追加することによって無効なスケジュールを有効にすることはできません（つまり、ツリーを削除する）。

問題を解決するには、これを簡単に修正する必要があります。ここで

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