如何从3个重叠列表中获取3个唯一项？
这与仅在每个列表中查找唯一或不同的项目不同。
我有3个引用对象列表，每个列表可以包含相同的项目(但每个项目只能包含一次)。我想要以下问题的是/否的答案:在每个列表中取一项，是否有可能没有重复项？
例如：
总榜单:苹果、梨、香蕉
清单一:苹果、梨
清单2:香蕉
清单三:香蕉、苹果
结果: TRUE (可以从每个列表中选择一个项目，并且有3个唯一的项目)
总榜单:苹果、梨、香蕉
清单一:苹果、梨
清单二:苹果、梨
清单三:苹果、梨
结果: FALSE (不能从每个列表中选择一项，并且不能有3个唯一项)
这是一个游戏，所以我需要它是有效的！提前谢谢。
回答 3
Stack Overflow用户
发布于 2016-04-29 19:08:39
这是NP-Hard problem Constraint satisfaction problem see here。换句话说，您有组{a，b，c，d}，并且您想要查找(a or b) and (b or c) and...
但是，如果您知道前面所有可能的选项，您可以创建一个值的列表\字典(较小列表的散列值)，并在运行时检查该列表。
如果没有，您可以使用其中一种CSP求解算法。
Stack Overflow用户
发布于 2016-04-29 19:16:39
假设你有list α，β和ɣ。
让ABC = α ∩ β ∩ ɣ
让AB = α ∩ β \ ABC
让AC = α ∩ ɣ \ ABC
让BC = β ∩ ɣ \ ABC
让A = α \ (β ∪ ɣ)
让B = β \ (α ∪ ɣ)
让C = ɣ \ (α ∪ β)
设| X |是集合X的基数。
当且仅当|A| + |B| + |C| + |AB| + |AC| + |BC| + |ABC| >= 3时返回true
示例实现：
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;
}Stack Overflow用户
发布于 2016-04-29 19:52:26
我认为你可以这样做：
你将整个列表中的第一项放在列表中，然后检查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个列表，那么你的check数组将包含n个元素。
https://stackoverflow.com/questions/36936413
复制相似问题
腾讯云开发者
