所有可能的礼物排列集合

本文关键字：排列 集合 礼物 有可能 | 更新日期: 2023-09-27 18:20:36

所以圣诞节快到了，每年我的家人都会从帽子上取下谁应该给谁买礼物的名字，而且总是会有人担心，主要是关于配偶为彼此买礼物。

假设这些家庭是这样的：

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

A家庭的人不能为家里的其他人购买，B、C、D家庭也是如此。

我们可以很容易地从一个特定的人那里得到一个家庭：

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

我们可以得到所有有效的配对：

var everyone = families.SelectMany(family => family);
var pairs = from giver in everyone
            from receiver in everyone
            where !families.FamilyOf(giver).Contains(receiver)
            select Tuple.Create(giver, receiver);

我如何将其转化为包括所有人的有效给予者/接受者的可能排列集合？我将从中随机选择一个集合。

所有可能的礼物排列集合

我写了一些代码来解决您的问题，但当它在挑选配对时有点"不走运"时，有时会抛出异常。例如，如果算法对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;
        }
    }
相关文章：