如何从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个元素。