查找A&B的不同合格组合,以及多对多A:B排除

Question

对于所有关于SO的"独特组合"和"笛卡尔产品"问题,我确信这个问题有一个名称和规范解决方案,但我并没有提出来.

更新......这是一个可能更好的例子:假设一个俱乐部有定期的抽奖活动.每个活动抽奖很多项目,会员每个项目购买门票.在抽奖的夜晚,抽奖经理打印出批量的名片,批次A,B,​​C等.当每件物品都被抽出时,他会将这些预先组装好的批次中的一个扔进料斗,混合起来,然后画一个名字.在赠送奖品之后,该名称将重新进入批次,如果任何其他项目恰好具有相同批次的参赛者,则重复使用该批次.问题:是否有无状态算法可以组装成批的名片,打印最少的卡片总数？[如果没有,Chris Shain的HashSet <>示例是我所知道的最有效的有状态替代方案.]

原始问题和示例:考虑以下人员,三明治和过敏症列表(存储关系;这些数据结构只是为了保持帖子简短,并不是问题或解决方案的固有内容):

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" } } };

为了找到可以吃特定三明治的人,我当然可以轻松地遍历三明治(外部)和人(内部)并检查是否过敏.

我想要什么,虽然是预先计算和发布的非过敏的人最小的列表组,将覆盖所有的三明治(人显然属于一组以上),不超过一组人的任何夹层,并最大限度地重复使用,例如,[Pete,Barb,Debbie,Frank,Sally]将涵盖面筋免费树枝和烤箱烤鸡.

举个例子,假设有一个三明治列表要抽出来.厨师制作一个,然后需要找出谁在抽奖(每个不过敏的人).我想要最少重复的一堆带橡皮圈的名片,捆绑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<string>。迭代一次 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);
}

那么当你需要查找对一组成分过敏的人时，你可以使用基于快速集合的 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