所有可能的收藏品列表

因此，圣诞节即将到来，我的家人每年都会从帽子上取名，以便谁应该为谁买礼物，并且总是存在顾虑，主要是配偶为彼此购买礼物。所有可能的收藏品列表

假设家庭都像这样：

List<List<string>> families = new List<List<string>>() 
{ 
    new List<string>() { "A1", "A2" }, 
    new List<string>() { "B1", "B2" }, 
    new List<string>() { "C1", "C2" }, 
    new List<string>() { "D1", "D2" } 
};

家庭一个让人无法购买别人在他们的家庭，同样适合家庭B，C，D

，我们就可以轻松搞定从给定的人有家人：

：

public static IEnumerable<string> FamilyOf(this List<List<string>> families, string person) 
{ 
    return families.Where(family => family.Contains(person)).First(); 
}

...我们可以得到所有有效的对

我怎样才能把它变成包含每个人的有效送达者/接收者的可能集合？从那我就选择一个随机集合。

来源

2014-09-03 Steven Evers

我会考虑模拟这种作为图形问题。人是有向图中的节点。箭头是“可以购买”的关系。为所有节点构造k-完全图，然后删除代表“非法”对的边。现在，为图中的每个节点选择一个出站箭头;当你这样做时，消除原始节点中的所有其他出站箭头以及所选节点中的所有入站箭头。没有人指向或指向没有人的节点的配置是非法的;拒绝它。 – 2014-09-03 06:22:34

我写了一些代码来解决你的问题，但是它有时会抛出一个异常，当它选择对时有点“不幸”。例如，如果算法配对A1B2 B1C2 C1A2 - >所以只剩下D1和D2，这会导致异常，因为它不再符合您的配对要求。

反正这里是代码，您可能要扩大，以防止它抛出一个异常：

 var everyone = families.SelectMany(family => family).ToList(); 
     everyone.Shuffle(); 
     var randPairs = families.SelectMany(family => family) 
      .Select(p => new { 
       Giver = p, 
       Receiver = everyone.PopRandom(x => !p.Contains(x[0])) 
      });

而对于IList的两种扩展方法：

public static T PopRandom<T>(this IList<T> list, Func<T, bool> predicate) 
    { 
     var predicatedList = list.Where(x => predicate(x)); 
     int count = predicatedList.Count(); 
     if (count == 0) 
     { 
      throw new Exception(); 
     } 
     T item = predicatedList.ElementAt(Rand.Next(count)); 
     while (item != null && !predicate(item)) 
     { 
      item = predicatedList.ElementAt(Rand.Next(list.Count)); 
     } 
     list.Remove(item); 

     return item; 
    } 

    public static void Shuffle<T>(this IList<T> list) 
    { 
     int n = list.Count; 
     while (n > 1) 
     { 
      n--; 
      int k = Rand.Next(n + 1); 
      T value = list[k]; 
      list[k] = list[n]; 
      list[n] = value; 
     } 
    }

来源

2014-09-03 12:32:54 Shiffty

所有可能的收藏品列表

回答

相关问题