找到 A 和 A 的不同合格组合B，具有多对多 A:B 排除

Question

对于所有关于 SO 的“不同组合”和“笛卡尔积”问题，我确信这个问题有一个名称和规范的解决方案，但我不会打开它。

更新...这是一个可能更好的示例：假设俱乐部定期举办抽奖活动。每个活动都会抽奖许多物品，会员按每个物品购买门票。在抽奖之夜，抽奖经理会打印出一批批名片，A批、B批、C批等。当每件物品被抽奖时，他将其中一批预先组装好的物品扔进料斗中，将其混合起来，并画出一个名字。颁发奖品后，该名称会返回到该批次中，如果任何其他项目碰巧有同一批次的参赛者，他会重复使用该名称。问题：是否有一种无状态算法可以批量组装名片，打印最少的名片总数？ [如果没有，Chris Shain 的 HashSet<> example 是我所知道的最有效的有状态替代方案。]

原始问题和示例：考虑以下人员、三明治和过敏的列表（以关系方式存储；这些数据结构只是为了保持帖子简短，并且不是问题或解决方案所固有的）：

var people = { "Pete", "Barb", "Debbie", "Frank", "Ralph", "Sally" };
var sandwiches = { "Peanut Butter", "Egg Salad", "Tuna Salad", "Oven Roasted Chicken", "Gluten-free Twigs" };
var allergies = {
    { "Pete", null }, 
    { "Barb", { "Peanut Butter" } }, 
    { "Debbie", { "Peanut Butter", "Egg Salad", "Tuna Salad" } }, 
    { "Frank", { "Egg Salad", "Tuna Salad" } }, 
    { "Ralph", { "Oven Roasted Chicken" } },
    { "Sally", { "Egg Salad", "Tuna Salad" } } };

为了找到可以吃给定三明治的人，我当然可以轻松地遍历三明治（外部）和人员（内部）并检查过敏情况。

不过，我想要的是预先计算并发布涵盖所有三明治的非过敏人群组的最小列表（人们显然会属于多个组），并且不超过一个任何三明治的一组人，并最大限度地重复使用，例如，组[皮特、巴布、黛比、弗兰克、莎莉]将涵盖无麸质树枝和烤箱烤鸡。

举个例子，假设有一份要抽奖的三明治清单。厨师做了一个，然后需要找出谁参加了抽奖（每个不过敏的人）。我想要一堆最少重复的橡皮筋名片集，捆绑 A、B、C 等等，这样就可以有一份三明治清单，每个三明治都指示要为该三明治扔哪一捆名片。想象一下名片纸真的很贵。 （显然，为了举例，我已经更改了问题域。）

我现在使用相当于人员集的哈希表来执行此操作，然后将指向这些集的指针填充到由三明治键入的字典中。它工作得很好，但感觉不优雅。

感谢任何能够说出这个问题并指出我采用更漂亮（或更教科书）方法的人。

更新：我正在使用相当于 MySQL 的 GROUP_CONCAT 来实现所需的最终结果。这并不理想，但我添加它是因为它澄清了所需的最终结果。在伪代码中：

// SandwichPeople = the sandwich list with a concatenated list of 
// people who can eat it:
SELECT Sandwich.SandwichName, GROUP_CONCAT(Person.FullName SEPARATOR ', ') as MemberNames
FROM Sandwich JOIN Person on [...not allergic...]

// SandwichRoster = distinct People from SandwichPeople with auto id
INSERT IGNORE INTO SandwichRoster (MemberNames) 
 SELECT DISTINCT MemberNames from SandwichPeople

// Match sandwiches with rosters:
SELECT SandwichPeople.SandwichName, SandwichRoster.ID
FROM SandwichPeople 
JOIN SandwichRoster on SandwichPeople.MemberNames = SandwichRoster.MemberNames

Answer 1

创建字符串键和 HashSet 值的字典。迭代一次 person->allergy 字典，对于每种过敏，在字典中获取或创建该过敏的记录：

// A dictionary containing the set of people who are allergic to any given thing
var allergyLookup = new Dictionary<String, HashSet<String>>();
allergies.ForEach(kvp => {
    var allergicSet = allergyLookup.ContainsKey(kvp.Value) ? allergyLookup[kvp.Value] : allergyLookup[kvp.Value] = new HashSet<String>();
    allergicSet.Add(kvp.Key);
}

然后，当您需要查找对一组成分过敏的人时，可以使用快速集-based exceptWith 函数：

var ingredients = { "Tuna", "Peanut Butter" };
var peopleWhoCanEatThis = new HashSet<String>(allPeople);
ingredients.ToList().ForEach(i => peopleWhoCanEatThis.ExceptWith(allergyLookup[i]));

HashSet 的 exceptWith() 函数比通用函数快得多，因为它是基于集合的，可以进行固定时间查找而不是线性时间查找。

编辑：错误地使用了 except 函数 - 快速设置减法是 exceptWith: http:// msdn.microsoft.com/en-us/library/bb299875.aspx