数字のグループの別の順列が必要です

Question

私は1から36までの数字を持っています。私がしようとしているのはのグループに3つのグループに入っていて、すべてのグループの順列があります。

各グループは数が順列

あたり、複数のグループに表示することができない1から36

に、12個の番号を含まなければならない。ここでの例である....

Permutation 1 
Group 1: 1,2,3,4,5,6,7,8,9,10,11,12 
Group 2: 13,14,15,16,17,18,19,20,21,22,23,24 
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36 

Permutation 2 
Group 1: 1,2,3,4,5,6,7,8,9,10,11,13 
Group 2: 12,14,15,16,17,18,19,20,21,22,23,24 
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36 

Permutation 3 
Group 1: 1,2,3,4,5,6,7,8,9,10,11,14 
Group 2: 12,11,15,16,17,18,19,20,21,22,23,24 
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36 

これらは3つの例で、私はそこに何百万/何十億もあると期待しています

Answer 1

以下の分析は、グループの順序が重要であると仮定しています。グループ化[{1}、{2}、{3}]はグループ化[{3}、{2}、{1}]とは区別されます（実際には、この数字の集合）。

あなたの場合、どのように進めますか？まず、最初のグループを選択する必要があります。これを行う方法は36通りありますが、（36！）/ [（12！）（24！）] = 1,251,677,700通りです。その後、第2のグループを選択する必要があります。これを行う方法は24通りありますが、（24！）/ [（12！）（12！）] = 2,704,156通りです。第2の選択肢はすでに第1の選択肢に条件付けられているので、3つのグループを掛け合わせる方法の総数を得ることができる。 36のプールから12の3つの等しいグループを選択する方法の総数は3,384,731,762,521,200です。あなたが8ビットのバイトを使用して数値を表現した場合、すべてのリストを格納するには少なくとも〜3のPentabytesが必要になります（リストのサイズは36バイトになりますので、〜108のようになります）。これは大量のデータであり、生成するのに時間がかかり、少量のディスクスペースを保存する必要がないため、これに注意してください。

これを実際に実装するには、それほど恐ろしいことではありません。しかし、私はこれが可能なら、SQLでこれを実装するのが難しいでしょう。 Pure SQLには、n^2個以上のエントリを返す操作（単純なクロス結合の場合）がありません。そのような膨大な数の結果を取得するには、多数の結合が必要です。さらに、純粋なSQLは一般的な再帰を行う能力がないため、さまざまな数の結合を行うことができないため、プロシージャを一般化するためにできるだけ私にストライキはありません。

手続き型言語を使用してグループ化を生成し、そのグループ化をデータベースに書き込むことができます。これがあなたの後のものかどうかはわかりません。あなたはそれが何をするかChoose([1...36], 12, 1, group1)のようにこれを呼び出す

n = 36 

group1[1...12] = [] 
group2[1...12] = [] 
group3[1...12] = [] 

function Choose(input[1...n], m, minIndex, group) 

    if minIndex + m > n + 1 then 
     return 

    if m = 0 then 

     if group = group1 then 
      Choose(input[1...n], 12, 1, group2) 

     else if group = group2 then 
      group3[1...12] = input[1...12] 
      print group1, group2, group3 

    for i = i to n do 

     group[12 - m + 1] = input[i] 
     Choose(input[1 ... i - 1].input[i + 1 ... n], m - 1, i, group) 

すべてのために、M = 0とグループ= GROUP1ため、コールChoose([?], 12, 1, group2)が行われた（その時点で、長さ12のサブ配列を命じたすべての可能性をGROUP1に記入ですグループ1の可能な選択、従って?）。これは、group2の長さ12の残りのすべての順序付き部分列を選択します。その時点でm = 0で、今度はgroup = group2になります。残りのエントリに安全にgroup3を割り当てることができます（group1とgroup2を選択した後にgroup3を選択する方法は1つだけです）。

再帰呼び出し（minIdx）の検索を開始するインデックスを伝播することによってのみ、順序付きサブシーケンスを取得します。同じ順序の12個のアイテムの順列を避けるために、順序付き部分シーケンスを取ります（順序はグループ内では関係ないため）。

ループ内のChooseへの各再帰呼び出しでは、1つの要素が削除されたinputが渡されます。ちょうど検討中のグループに追加された要素。

minIndex + m > n + 1をチェックし、この場合は入力にあまりにも多くの項目をスキップして現在のグループを12個の項目で埋めることができるため、再帰を早期に停止します（順序付けするサブシーケンスを選択します） 。

私は12/36/3グループの仮定をプログラムのロジックにハードコーディングしていることに気づくでしょう。これは、簡潔さと明快さのために行われました。入力サイズNとグループ化するkの数をパラメータ化することができないためではありません。これを行うには、グループの配列（それぞれN/kのサイズのkグループ）を作成し、12ではなくN/kでChooseを呼び出し、if/then/elseの代わりにselect/switch caseステートメントを使用する必要があります再度Chooseかどうかを判断するか、印刷します。しかし、それらの細部は練習として残すことができます。