要素を繰り返すことなくペアのセットから組み合わせを生成する

https://cs.stackexchange.com/questions/11

algorithms

16-10-2019
|

質問

ペアのセットがあります。各ペアは、x、yが範囲の整数に属するような形式（x、y）です [0,n).

したがって、nが4の場合、次のペアがあります。

(0,1) (0,2) (0,3)
(1,2) (1,3) 
(2,3)

私はすでにペアを持っています。今、私は使用して組み合わせを構築する必要があります n/2 整数のいずれも繰り返されないようにペア（言い換えれば、各整数は最終的な組み合わせで少なくとも1回表示されます）。以下は、より良い理解のための正しい組み合わせと誤った組み合わせの例です

 1. (0,1)(1,2) [Invalid as 3 does not occur anywhere]
 2. (0,2)(1,3) [Correct]
 3. (1,3)(0,2) [Same as 2]

ペアができたら、誰かが私にすべての組み合わせを生成する方法を提案できますか。

解決

直接的な方法の1つは、各呼び出しで次のことを行う再帰手順です。手順への入力は、すでに選択されているペアのリストとすべてのペアのリストです。

入力リストでまだカバーされていない最小数を計算します。最初の呼び出しでは、ペアが選択されていないため、これは0の場合です。
すべての番号がカバーされている場合は、正しい組み合わせがあり、印刷して前のステップを返します。それ以外の場合、明らかにされている最小の数は、私たちが目指すターゲットです。
ターゲット番号をカバーする方法を探して、ペアを検索します。何もない場合は、以前のレベルの再帰に戻ってください。
ターゲット番号をカバーする方法がある場合は、最初の方法を選択して、手順全体を再度呼び出します。選択したペアのリストにペアを選択してください。
それが戻ったら、を探します次以前に選択したペアと重複することなく、ターゲット番号をペアでカバーする方法。見つけたら、それを選択して、再び次の手順を再帰的に呼び出します。
ターゲット番号をカバーする方法がなくなるまで、手順4と5を続けます。ペアのリスト全体を調べます。これ以上正しい選択がない場合は、再帰の以前のレベルに戻ります。

このアルゴリズムを視覚化する方法は、パスが重複しないペアのシーケンスであるツリーを使用します。ツリーの最初のレベルには、0を含むすべてのペアが含まれています。上記の例では、木は

           Root
             |
     ----------------
     |       |       |
   (0,1)   (0,2)   (0,3)
     |       |       |
   (2,3)   (1,3)   (1,2)

この例では、ツリーを通るすべてのパスが実際に正しいコレクションを提供しますが、たとえば、ペア（1,2）を除外した場合、右端のパスには1つのノードしかなく、ステップ3の障害の検索に対応します。

このタイプの検索アルゴリズムは、特定のタイプのすべてのオブジェクトを列挙するという多くの同様の問題に対して開発できます。

おそらくOPがそれを意味することが示唆されました全て質問が言うように、ペアはそれらのセットだけでなく、入力に含まれています。その場合、どのペアが許可されているかを確認する必要がなくなったため、アルゴリズムははるかに簡単です。すべてのペアのセットを生成する必要さえありません。次のPseudocodeは、OPが尋ねたことを行います。ここでは、$ n $は入力番号、「リスト」が空のリストとして始まり、「カバー」は0に初期化された長さ$ n $の配列です。

sub cover {
  i = 0;
  while ( (i < n) && (covered[i] == 1 )) {
   i++;
  }
  if ( i == n ) { print list; return;}
  covered[i] = 1;
  for ( j = 0; j < n; j++ ) {
    if ( covered[j] == 0 ) {
      covered[j] = 1;
      push list, [i,j];
      cover();
      pop list;
      covered[j] = 0;
    }
  }
  covered[i] = 0;
}

他のヒント

繰り返し解決できます。範囲$ [0、n）$のすべてのソリューション$ s_n $があるとします。次に、$ s_n $からソリューション$ s_ {n+2} $を簡単に作成できます。サイズは$ n $で非常に急速に成長するため、すべてのセットをメモリに保持するのではなく、ジェネレーターを書くのは良いことかもしれません。以下のPythonの例を参照してください。

def pairs(n):
    if (n%2==1 or n<2):
        print("no solution")
        return
    if (n==2):
        yield(  [[0,1]]  )
    else:
        Sn_2 = pairs(n-2) 
        for s in Sn_2:
            yield( s + [[n-2,n-1]] )
            for i in range(n/2-1):
                sn = list(s)
                sn.remove(s[i])
                yield( sn + [ [s[i][0], n-2] , [s[i][1], n-1] ] )
                yield( sn + [ [s[i][1], n-2] , [s[i][0], n-1] ] )

呼び出しによってすべてのペアをリストできます

for x in pairs(6):
   print(x)

アップデート: ：私の以前の回答は、OPが尋ねていなかったBipartiteグラフを扱っていました。関連情報として、今のところそれを残しています。しかし、より適切な情報は、非副党グラフの完全なマッチングに関連しています。

この点について、 Proppによる素晴らしい調査がありますそれは進捗状況の概要を示しています（1999年まで）。その記事のいくつかのアイデアと関連するリンクは、有用であることが証明されるかもしれません。 tl; dr is-それはトリッキーです:)

---古い答えの始まり

あなたがすることを求めていることは、二部グラフで可能なすべての完璧なマッチングを列挙することです。これを行うための多くの異なるアルゴリズムがあり、特に最近のアルゴリズムの1つは ISAAC 2001.

基本的なアイデアは、ネットワークフローを使用して1つの完全なマッチングを見つけ、交互のサイクルを使用してこれを繰り返し変更することです（詳細については、ネットワークフローに関するアルゴリズムの教科書の章を参照してください）。

選択するすべてのペアは、もう選択できない2つの行を排除します。このアイデアを使用して、再帰アルゴリズム（SCALAで）をセットアップできます。

def combine(pairs : Seq[(Int,Int)]) : Seq[Seq[(Int, Int)]] = pairs match {
  case Seq() => Seq()
  case Seq(p) => Seq(Seq(p))
  case _ => {
    val combinations = pairs map { case (a,b) => {
      val others = combine(pairs filter { case (c,d) =>
        a != c && a != d && b != c && b != d
      })

      others map { s => ((a,b) +: s) }
    }}

    combinations.flatten map { _.sorted } distinct
  }
}

これは確かにより効率的な方法で表現できます。特に、組み合わせの行全体を考慮する必要がないという考えは、 filter.

質問にはすでに多くの素敵なanswersがありますが、基本的な一般的なトリックを指摘するのはいいことだと思います。

組み合わせる要素の合計注文を持つことができる場合、一意の組み合わせを生成する方がはるかに簡単です. 。これにより、ソートされた組み合わせのみを許可する場合、一意性が保証されます。ソートされた組み合わせも生成するのは難しくありません。通常のブルートフォース列挙検索を行うだけですが、各ステップでは、各ステップで既に選ばれた要素よりも大きい要素のみを選択します。

この特定の問題の余分な合併症は、長さn/2（最大長）の組み合わせのみを取得したいという欲求です。良い選別戦略を決定した場合、これは難しくありません。たとえば、Carl Mummmetの答えで指摘されているように、辞書版の種類を考慮すると（質問の図のトップダウン、左右）、次の要素を常に取得する戦略を導き出し、その最初の数字が常に次の要素を取るという戦略を導き出します。まだ小さな未使用数。

他の長さのシーケンスを生成したい場合は、この戦略を拡張することもできます。最初の数値が利用可能な最小の要素ではない次の要素を選択するときはいつでも、ソートされたサブシーケンスに表示される要素の1つ以上の要素を除外して、それに応じてプレミューティングの最大長が減少することを忘れないでください。

これがあなたが尋ねているかどうかはわかりませんが、私が理解しているように、あなたはすべて$ n を選択しています$ [n] = {1、 cdots、n } $の2つの並べ替えられたペアがあり、リストをカウントしたいセット$ [n] $をカバーするすべてのペアのうち、$ n $は偶数です。これをと考えることができますエッジカバリング $ k_n $、$ n $ verticesの完全なグラフ。

さらに、質問は、$ [n] $の各数値がリストに一度だけ表示されると仮定しているようです。その場合、私たちは完璧なマッチ. 。グラフ内の一致の数は永続その隣接マトリックス. 。したがって、$ mathsf {perm}（k_n）$を計算する必要があります。

永続的であることが知られています $ mathsf {＃p text { - } complete} $ , 、しかし、これは一般的な場合です。 $ k_n $には、$ frac {n！} {2^{ frac {n} {2}}} $そのようなリストがあります。

~~これらすべてを生成する最も簡単な方法は、1つの完全な一致を修正し、$ [n] $の順列を適用することですが、これにより多くの重複が生成されます。~~

ライセンス： CC-BY-SA と帰属

所属していません cs.stackexchange