2

N セットの値があります。

  • S1 = {A、B、C、D、E}
  • S2 = {A、B、C、D、E、F}
  • S3 = {A,B}
  • S4 = {C、E、F、G、H}

コレクションの各セットに個別の値または一意の値があるかどうかを知りたいです...つまり。他にはない各セットに少なくとも1つの値を残すセットを通る「パス」はありますか..上記の例に対する答えは、S1からのB、S2からのD、S2からのAなど、TRUEになります。 S3 と S4 からの C

FALSE の例は次のようになります。

  • S1 = {A、B、C}
  • S2 = {A}
  • S3 = {A,B}
  • S4 = {A,C}

セット間で値を複製する必要があるためです。

いつものように、この問題には些細な解決策があるに違いないと確信しています。どんな助けでも非常に感謝しています。ありがとうございました

明確化

これまでの回答に感謝しますが、（私が思うに）単純な要件があるにもかかわらず、私はまだこれに少し混乱しています。私は、質問が実際に表している問題よりも紛らわしいように聞こえる質問をしたと思います。

明確にするために、私の最終目標は次のとおりです。

  • 各セットから 1 つの値を取得します。
  • この新しい値のリストは、互いに区別する必要があります。
  • 各セットから選択される値は比較的恣意的です。
  • 入力セットから単一の個別の値を導出できない場合、プロセスは何も返さないようにする必要があります。

二部グラフと最大フローについて読んだことがありますが、「木からの木」をまったく見ることができません。最終的には、これを実装するために .NET でコードを記述する必要があるため、それが不可能な場合は、擬似コードが非常に役立ちます。関連するアルゴリズムが実際に動作している簡単な例があれば素晴らしいでしょう。

4

3 に答える 3

3

で 2 部グラフを作成します。

Set X containing value of nodes = {S1,S2,S3,...,SN}
Set Y containing value of nodes = {A,B,C...}

問題で与えられたセットに従ってエッジを作成することにより、このグラフを問題のステートメントに一致させます。

問題は、X と Y の間の「最大 (2 部) マッチング」が N に等しいかどうかを確認することになります。値の割り当てを知る必要がある場合は、このマッチングも出力します。

編集（詳細説明用）

ここに画像の説明を入力

2 つのセットの間のエッジは、元のセットを示します。X のすべての頂点がカバーされ、2 つのエッジが共通の頂点を共有しないように、エッジを見つける必要があります。

注: 最大一致が複数存在する場合があります

于 2012-09-02T21:07:33.090 に答える
1

あなたの要件はこれだと思います：

セットS1、S2、 ...、 を呼び出しますSn。要素a1、a2、 ...、 を呼び出しますam。次に、次のことを行います。

  • ごとSに、それを含まないメンバーが少なくとも 1 つあるように、 のメンバーを選択します。aSSa

あなたの例では：

  • S1 ピック B( にはありませんS4)
  • S2 ピック D( にはありませんS3)
  • S3 ピック A( にはありませんS4)
  • S4 ピック C( にはありませんS3)

これを解決するために、可能なアプローチは次のとおりです。

  • Ss とメンバーs を反復処理し、それらが出現する s の数とともに、見られるaすべての個別の s を追跡しますaS
  • s をもう一度反復し、それぞれについて、カウントが s の総数より小さいSメンバーの構築されたカウント リストを調べます。この要件を満たす任意のものを選択してくださいanSa

これで完了です。

あなたのコメントから、「「A」が複数のセットに存在する場合、「A」をセットの1つに残す必要がある」という追加の要件があるようです。

  • a複数のメンバーであるそれぞれについてS、それaはいくつかの「選択された」メンバーですS

ただしE、あなたの例では、複数に存在するSが決して選択されないという事実でコメントを二乗する方法がわかりません。

于 2012-09-03T10:38:45.290 に答える
0

最初の例のデータをテーブルの形式で表現しましょう。

    a   b   c   d   e   f   g   h
s1  .   .   .   .   .
s2  .   .   .   .   .   .
s3  .   .
s4          .       .   .   .   .

ここで、たとえば次のような解決策を探しています（質問から取得）：

s1=b, s2=d, s3=a, s4=c

マーク付きのソリューション (1 つの列に 2 つの X を含めることはできません):

    a   b   c   d   e   f   g   h
s1  .   X   .   .   .
s2  .   .   .   X   .   .
s3  X   .
s4          X       .   .   .   .

割り当て問題でプロセッサのタスクを選択するのと似ています...

しかし、複雑さを気にしないのであれば、考えられるすべての構成をチェックしてみてはどうでしょうか?

for (every element in s1) as e1
    for (every element in s2) as e2
        for (every element in s3) as e3
            for (every element in s4) as e4
                if (e1 != e2 != e3 != e4)
                    return true;
return false;

複雑さを伴う些細な力ずくO(s1.length * s2.length * s3.length * s4.length)です。

于 2012-09-02T20:15:59.490 に答える