如何從3個重疊列表中獲得3個獨特的項目？

Question

這與在每個列表中查找唯一或不同的項目不同。

我有3個引用對象列表，每個列表可以包含相同的項目（但只能包含每個項目一次）。我想對以下問題做出肯定/否定的回答：在每個列表中取一個項目，是否有可能沒有重複項目？

例如：

總體列表：蘋果，梨，香蕉

列表1：蘋果，梨

列表2：香蕉

列表3：香蕉，蘋果

結果：TRUE（可以從每個列表中選擇一個項目並擁有3個獨特項目）

總體列表：蘋果，梨，香蕉

表1：蘋果，梨

表2：蘋果，梨

表3：蘋果，梨

結果：FALSE（不能選擇每個列表中有一個項目，並有3個獨特的項目）

這是一個遊戲，所以我需要它是高效的！提前致謝。

Answer 1

這是NP-Hard問題Constraint satisfaction problemsee here。 換句話說，你有{a，b，c，d}組，並且你想找到(a or b) and (b or c) and...

但是，如果你知道所有可能的選項，你可以創建一個list \ dictionary的值（哈希值對於較小的列表），只需在運行時檢查列表。

如果不是，您可以使用其中一種CSP求解算法。

Answer 2

讓我們說你有名單α，β和ɣ。

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

讓| X |是集合X的基數。

返回true，當且僅當|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個元素） - 例如0表示不發生，1表示發生。 然後再對整個列表中的第二項進行此操作，依此類推。 所以你最終會得到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 1 0的校驗數組，並且當您將每個這些數組的第三個元素相加時，您將得到0.

我認爲這可以很容易地擴展到儘可能多的目標列表，如果你有n個列表，你的檢查數組將包含n個元素。