リスト内の要素のすべての組み合わせを取得するにはどうすればよいですか？

Question

X要素のリストを取得するとき、どのようにしてこれらの要素のすべての倍精度化、三重化、...（Y）の組み合わせを取得できますか？
Yは必要な組み合わせのサイズです。例：Y = 2の場合は、すべてのペアを取得する必要があります。
同じ組み合わせを2回与えないでください（例：[a、b]と[b、a]は同じ組み合わせです）

Answer 1

リストをコピーしてください。

リストが空の場合、組み合わせはありません。

サイズ1のすべての組み合わせを取得するには、各要素を順番に調べます。

サイズn + 1のすべての組み合わせを取得するには、最初に最初の要素を削除します。その後、残りのリストのサイズnとその最初の要素のすべての組み合わせを取得します。その後、残りのリストのサイズn + 1のすべての組み合わせを取得し、最初の要素を追加しないでください。

これで完了です。

あなたは気に入って、最適化のために要素をコピー/除去するふりをするだけです。

Answer 2

あなたは2からYに対するTを反復し、サイズXバックに前方及びT 1SにXtの0で埋める持つ配列Aを作成し、その後、以下のコードを有することができる：

do{ 
    //1s in array A now correspond to a valid combination 
}while(std::next_permutation(A,A+X)); 

ループは、サイズtのすべての組み合わせが反復されると停止する。

next_permutationは、アルゴリズムを次の辞書順に並べ替えるか、配列が辞書編集上最も大きな順列になっている場合はfalseを返す。その複雑さはO（n）です。なぜなら、配列を一度反復する必要があるからです。だから問題にはならないでしょう。プロセス全体の複雑さの合計は、O（2^n * n）によって制限されます。だからここ

は、例えば、擬似コード

D[X] = {1,2,3,4} Y = 3 //the input 
For t = 2,3,..,Y 
    A[X] = {0,...,0,1,...,1} // X - t 0s and t 1s 
    Do 
     For j = 0,1,...,X-1 
      if A[j] == 1 
       output D[j] 
      end if 
     end for 
     output newline 
    While next_permutation(A,A+X) 
end for 

が出力意志が

3 4 
2 4 
2 3 
1 4 
1 3 
1 2 
2 3 4 
1 3 4 
1 2 4 
1 2 3