c# - 找到 A 和 B 的不同合格组合，多对多 A :B exclusions

Question

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

更新...这是一个可能更好的例子:假设一个俱乐部有定期的抽奖事件。每个事件都会抽奖许多项目，成员(member)按项目购买门票。在抽奖之夜，抽奖经理打印出名片批处理，批处理 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] 将涵盖无麸质 Twig 和 toastr 烤鸡。

例如，假设有一份三明治 list 需要抽奖。厨师做了一个，然后需要找出谁在抽奖(每个不过敏的人)。我想要一组重复最少的橡皮筋名片，捆绑 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