algorithm - アルゴリズム - 各配列の要素が異なることを効率的に確認する方法は?

Question

この質問のタイトルの書き方がわかりません。既存のタイトルは正確ではない可能性があります。

問題は次のとおりです。

グループ (配列)がmあります。たとえば、4 つのグループがあります。各グループにはいくつかの数字が含まれています。私たちが望むのは、各グループが 1 つの数字を出し、結果として得られる合計 4 つの数字 (それぞれが 1 つのグループからのもの) が異なることです。

これら 4 つのグループが与えられた場合、それらが私たちの希望に合っていることを確認するにはどうすればよいでしょうか?

例えば、

A: 0、2、3

B: 0、2

子：2、3

D: 1

上記の4つのグループは、私たちの希望に合うことができます. D は 1、C は 3、B は 2、A は 0 を返します。

しかし、もし

あ：2

B: 2

子：2、3

D: 1

悪いです。各グループに個別の番号を与えることはできません。

私の考えは、すべてのグループのすべての要素をバックトラックして、要素のすべての組み合わせを取得し、1 つの組み合わせの要素が異なるかどうかを確認する最も愚かな方法です。

誰もがより良い考えを持っていますか?

score 5 · Accepted Answer

これをネットワークフロー問題としてモデル化し、 Edmunds-Karpやpush-relabelなどの問題ドメイン（多くは多項式時間）で高速アルゴリズムを使用できます。

ソースノードとシンクノードを作成します。次に、「グループ」ごとおよび個別の要素ごとにノードを作成します。各グループノードをソースに接続し、各要素ノードをシンクに接続します。最後に、グループが要素である場合は、グループノードを要素ノードに接続します。すべてのフロー容量は1である必要があります。

これは例で最もよく説明されています。あなたが与えた最初の例を使用します：

A: 0, 2, 3
B: 0, 2
C: 2, 3
D: 1

次のフローネットワークになります。

   A   0
  /     \
 /       \
S--B   1--T
 \       /|
  \     / |
   C   2 /
        /
       3

中間の流れを描くことができませんでした。ただし、Aが0、2、3に流れ、Bが0、2に流れ、Cが2、3に流れ、Dが1に流れると想像してください。すべての流れは単位容量です。

したがって、最初にこのグラフで最大フローを見つけます。グループと要素の間のフローにより、必要な2部マッチングが得られます。

一致する可能性がない場合、最大フローはグループの数より少なくなります。

score 2 · Accepted Answer

score 0 · Accepted Answer

1 つのアイデアは、すべてのグループに固有の要素を探し、それらが属するグループに使用することです。これにより、共通の要素を持つグループのみにリストが絞り込まれます。
もう 1 つのアイデアは、最小の要素 (理想的には 1 つ) を持つグループから開始し、それらを値の 1 つに設定し、サイズを増やして反復することです (既に使用されている要素を削除した後にサイズを考慮することができます)。

3 に答える 3