1

要素のソートされたリストが与えられ、ある条件を満たすすべてのサブセットを生成したいとします。そのため、特定のセットが条件を満たさない場合、より大きなサブセットもそれを満たさず、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 の最初の要素がありません。2 番目の呼び出し (プルーニング条件に違反していない場合) によって追加されたサブセットにはその要素があるため、2 つの交差生成されたサブセットのセットは空です。

于 2009-06-01T18:34:04.747 に答える
2

サブセットの 1 つ (およびそのすべてのスーパーセット) が条件を満たさない場合は、再帰的な実行行をあきらめて、空のセットから始めてさらに要素を追加しようとして、セットを再帰的に構築することができます。リストしたい条件を満足する部分集合を持つセット 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

再帰関数を使用してサブセットを生成する、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 に答える
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

確かにそれを行う方法はありますが、何らかの方法で条件を制約できない限り、O(2^n) の手順が必要になります。たとえば、すべてのサブセットが選択される 1 ～ 100 の条件を考慮すると (たとえば、< Σ i for i for i in 1- n )、すべてのサブセットを列挙することになります。

あなたは見ているでしょう

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

0 から s n -1 までのすべての 2 進数を生成し、ビット i が 1 のときにサブセットの要素 i を選択するだけで、集合のべき集合を取得できます。

于 2009-06-01T18:20:22.883 に答える
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 に答える