3つの重複するリストから3つのユニークなアイテムを取得するにはどうすればよいですか？

Question

これは、各リストで一意のアイテムまたは別個のアイテムを見つけることとは異なります。

私は参照オブジェクトの3つのリストを持ち、それぞれのリストには同じアイテムを含めることができます（しかし、各アイテムは1回だけ含めることができます）。次の質問にはい/いいえの回答が必要です：各リストで1つの項目を取ると、重複がない可能性はありますか？

例えば：

全体のリスト：リンゴ、梨、バナナ

リスト1：リンゴ、梨

リスト2：バナナ

リスト3：バナナ、リンゴ

結果：TRUE（各リストから1つのアイテムを選択でき、固有のアイテムが3つあります）

全体のリスト：リンゴ、梨、バナナ

リスト1：リンゴ、梨

リスト2：リンゴ、梨

リスト3：リンゴ、梨

結果：FALSE（選択することはできません各リストから1つのアイテムがあり、固有のアイテムが3つあります）

これはゲーム用ですので効率的にする必要があります！前もって感謝します。

Answer 1

これはNP-Hardの問題Constraint satisfaction problemsee hereです。 つまり、あなたはグループ{a、b、c、d}を探しています。(a or b) and (b or c) and...

しかし、可能なすべてのオプションが分かっていれば、値のリスト\辞書（ハッシュ値小さなリストの場合）、実行時にリストをチェックするだけです。

もしそうでなければ、CSP解決アルゴリズムの1つを使用できます。

Answer 2

のは、あなたがリストα、βとɣを持っていると言いましょう。 X |

ABC = α ∩ β ∩ ɣ
がAB = α ∩ β \ ABC
がAC = α ∩ ɣ \ ABC
がBC = β ∩ ɣ \ ABC
がA = α \ (β ∪ ɣ)
がB = β \ (α ∪ ɣ)
がC = ɣ \ (α ∪ β)

レッツをしてみましょうしましょうしましょうしましょうしましょうしましょうしましょう|集合Xの基数である。

真リターン場合にのみ、 |A| + |B| + |C| + |AB| + |AC| + |BC| + |ABC| >= 3

実装例

：あなたはあなたの全体的なリストの最初の項目を取り、その後、チェック

：

void Main() 
{ 
    var alpha = new List<string> { "apple", "pear", }; 
    var beta = new List<string> { "banana", }; 
    var gamma = new List<string> { "banana", "apple", }; 

    Console.WriteLine(Compute(alpha, beta, gamma)); 
    Console.WriteLine(ComputeWithSets(alpha, beta, gamma)); 

    alpha = new List<string> { "apple", "pear", }; 
    beta = new List<string> { "apple", "pear", }; 
    gamma = new List<string> { "apple", "pear", }; 

    Console.WriteLine(Compute(alpha, beta, gamma)); 
    Console.WriteLine(ComputeWithSets(alpha, beta, gamma)); 

    alpha = new List<string> { "apple", "pear", "banana", }; 
    beta = new List<string> { "apple", "pear", "banana", }; 
    gamma = new List<string> { "apple", "pear", "banana", }; 

    Console.WriteLine(Compute(alpha, beta, gamma)); 
    Console.WriteLine(ComputeWithSets(alpha, beta, gamma)); 
} 

bool Compute(List<string> alpha, List<string> beta, List<string> gamma) 
{ 
    if (alpha.Count == 0) return false; 
    if (beta.Count == 0) return false; 
    if (gamma.Count == 0) return false; 

    foreach (var a in alpha) 
     foreach (var b in beta) 
      if (a != b) 
       foreach (var c in gamma) 
        if (c != a && c != b) 
        { 
         Console.Write(string.Format("{0},{1},{2} =>", a, b, c)); 
         return true;  
        } 
    return false; 
} 

bool ComputeWithSets(List<string> alpha, List<string> beta, List<string> gamma) 
{ 
    var abc = alpha.Intersect(beta.Intersect(gamma)); 
    var abcCardinality = abc.Count(); 

    var count = abcCardinality; 
    if (count >= 3) return true; 

    var ab = alpha.Intersect(beta).Except(abc); 
    count += ab.Count(); 
    if (count >= 3) return true; 

    var bc = beta.Intersect(gamma).Except(abc); 
    count += bc.Count(); 
    if (count >= 3) return true; 

    var ac = alpha.Intersect(gamma).Except(abc); 
    count += ac.Count(); 
    if (count >= 3) return true; 

    var a = alpha.Except(ab).Except(ac).Except(abc); 
    count += a.Count(); 
    if (count >= 3) return true; 

    var b = beta.Except(ab).Except(bc).Except(abc); 
    count += b.Count(); 
    if (count >= 3) return true; 

    var c = gamma.Except(ac).Except(bc).Except(abc); 
    count += c.Count(); 
    if (count >= 3) return true; 

    return false; 
} 

Answer 3

私は次のようにあなたがそれを行うことができると思いますあなたの3つの "ターゲット"リストのそれぞれは、どの要素が発生しているかを調べるために使用します。これらのチェック結果を3要素配列（ターゲットリストごとに1要素）に格納します。 次に、全体のリストの2番目の項目についてこれを再度実行します。 3つの要素配列の "チェックリスト"になります（リストの長さは、配列全体の要素数に等しい） チェックリストの各配列の最初の要素を合計し、2番目の要素および第3の構成元素限り、各合計は、あなたのテストに合格した0以上であると、あなたの最初の例

例えば 全体のリスト：リンゴ、梨、バナナ

Check results: 
Item 1 (apple) : 1 0 1 (apple occurs in list 1 and 3) 
Item 2 (pear) : 1 0 0 
Item 3 (banana) : 0 1 1 
Total    2 1 2 (result is a pass) 

あなたの第二の例は失敗します1つのチェック配列が110個あり、これらの配列のそれぞれから3番目の要素を追加すると0が得られるからです。

これは、あなたが望む数のターゲットリストに簡単に拡張できると思います。リストがn個ある場合、チェック配列にはそれぞれn個の要素が含まれます。