用于检索两个列表的每个可能的子列表组合的算法

Question

假设我有两个列表,如何遍历每个子列表的每个可能组合,这样每个项目只出现一次.

我想一个例子可能是你有员工和工作,你想把他们分成团队,每个员工只能在一个团队中,每个工作只能在一个团队中.例如

List<string> employees = new List<string>() { "Adam", "Bob"}  ;
List<string> jobs      = new List<string>() { "1", "2", "3"};

我想要

Adam       : 1
Bob        : 2 , 3

Adam       : 1 , 2
Bob        : 3

Adam       : 1 , 3
Bob        : 2

Adam       : 2 
Bob        : 1 , 3

Adam       : 2 , 3
Bob        : 1

Adam       : 3
Bob        : 1 , 2

Adam, Bob  : 1, 2, 3

我尝试使用这个 stackoverflow问题的答案来生成每个可能的员工组合和每个可能的工作组合的列表,然后从每个列表中选择一个项目,但这就是我得到的.

我不知道列表的最大大小,但肯定会小于100,可能还有其他限制因素(例如每个团队的员工人数不超过5人)

更新

不确定这是否可以更多和/或简化,但这是我到目前为止所得到的.

它使用Yorye提供的Group算法(参见下面的答案),但我删除了我不需要的orderby,如果键不可比,则会导致问题.

var employees = new List<string>() { "Adam", "Bob"  } ;
var jobs      = new List<string>() { "1", "2", "3"  };

int c= 0;
foreach (int noOfTeams in Enumerable.Range(1, employees.Count))
{   
    var hs = new HashSet<string>();

    foreach( var grouping in Group(Enumerable.Range(1, noOfTeams).ToList(), employees))
    {   
        // Generate a unique key for each group to detect duplicates.   
        var key = string.Join(":" , 
                      grouping.Select(sub => string.Join(",", sub)));           

        if (!hs.Add(key))
            continue;

        List<List<string>> teams = (from r in grouping select r.ToList()).ToList();

        foreach (var group in Group(teams, jobs))
        {
            foreach (var sub in group)
            {               
                Console.WriteLine(String.Join(", " , sub.Key )   + " : " + string.Join(", ", sub));
            }
            Console.WriteLine();
            c++;
        }
    }

}           
Console.WriteLine(String.Format("{0:n0} combinations for {1} employees and {2} jobs" , c , employees.Count, jobs.Count));  

由于我并不担心结果的顺序,这似乎给了我我需要的东西.

Answer 1

好问题。

首先，在写下代码之前，让我们了解问题的基本组合。

基本上，您要求对于集合 A 的任何分区，您需要集合 B 中相同数量的部件。

例如，如果您将集合 A 拆分为 3 个组，则需要将集合 B 也拆分为 3 个组，如果您不这样做，则至少有一个元素在另一组中不会有相应的组。
将 A 组拆分为 1 组更容易想象，我们必须像您的示例 (Adam, Bob : 1, 2, 3) 中那样从 B 组制作一组。

所以现在，我们知道集合 A 有n 个元素，而集合 B 有k 个元素。
所以自然我们不能要求任何集合被分割得更多Min(n,k)。

假设我们将两个集合分别分成 2 个组（分区），现在我们1*2=2!在两个集合之间有唯一的对。
另一个例子是 3 个组，每个组都会给我们1*2*3=3!独特的配对。

然而，我们还没有完成，在任何一个集合被分成几个子集（组）之后，我们仍然可以以多种组合对元素进行排序。
因此，对于m集合的分区，我们需要找到n在m分区中放置元素的组合数。
这可以通过使用第二类公式的斯特林数找到：

（方程 1）

此公式为您提供了将一组n元素划分k为非空集的方法数。

因此，从 1 到所有分区的对组合总数min(n,k)为：（

等式 2）

简而言之，它是两个集合的所有分区组合的总和，乘以所有对的组合。

所以现在我们了解了如何对我们的数据进行分区和配对，我们可以写下代码：

代码：

所以基本上，如果我们看看我们的最终方程 (2)，我们就会明白我们的解决方案需要四部分代码。
1. 求和（或循环）
2. 一种从两个集合中获得我们的斯特林集或分区
的方法 3. 一种获得两个斯特林集的笛卡尔积的方法。
4. 一种排列集合项的方法。(n!)

在 StackOverflow 上，您可以找到许多关于如何排列项目以及如何查找笛卡尔积的方法，这是一个示例（作为扩展方法）：

 public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> list)
    {
        if (list.Count() == 1)
            return new List<IEnumerable<T>> { list };

        return list.Select((a, i1) => Permute(list.Where((b, i2) => i2 != i1)).Select(b => (new List<T> { a }).Union(b)))
                   .SelectMany(c => c);
    }

这是代码中最简单的部分。
更困难的部分（恕我直言）是找到n一个集合的所有可能的分区。
所以为了解决这个问题，我首先解决了一个更大的问题，即如何找到一个集合的所有可能的分区（不仅仅是大小为 n）。

我想出了这个递归函数：

public static List<List<List<T>>> AllPartitions<T>(this IEnumerable<T> set)
    {
        var retList = new List<List<List<T>>>();

        if (set == null || !set.Any())
        {
            retList.Add(new List<List<T>>());
            return retList;
        }
        else
        {
            for (int i = 0; i < Math.Pow(2, set.Count()) / 2; i++)
            {
                var j = i;

                var parts = new [] { new List<T>(), new List<T>() };


                foreach (var item in set)
                {
                    parts[j & 1].Add(item);
                    j >>= 1;
                }

                foreach (var b in AllPartitions(parts[1]))
                {
                    var x = new List<List<T>>();

                    x.Add(parts[0]);

                    if (b.Any())
                        x.AddRange(b);

                    retList.Add(x);
                }
            }
        }
        return retList;
    }

: 的返回值List<List<List<T>>>仅表示所有可能分区的列表，其中一个分区是一个集合列表，一个集合是一个元素列表。
我们不必在这里使用 List 类型，但它简化了索引。

所以现在让我们把所有东西放在一起：

主要代码

//Initialize our sets
        var employees = new [] { "Adam", "Bob" };
        var jobs = new[] {  "1", "2", "3" };

        //iterate to max number of partitions (Sum)
        for (int i = 1; i <= Math.Min(employees.Length, jobs.Length); i++)
        {
            Debug.WriteLine("Partition to " + i + " parts:");

            //Get all possible partitions of set "employees" (Stirling Set)
            var aparts = employees.AllPartitions().Where(y => y.Count == i);
            //Get all possible partitions of set "jobs" (Stirling Set)
            var bparts = jobs.AllPartitions().Where(y => y.Count == i);

            //Get cartesian product of all partitions 
            var partsProduct = from employeesPartition in aparts
                      from jobsPartition in bparts
                               select new {  employeesPartition,  jobsPartition };

            var idx = 0;
            //for every product of partitions
            foreach (var productItem in partsProduct)
            {
                //loop through the permutations of jobPartition (N!)
                foreach (var permutationOfJobs in productItem.jobsPartition.Permute())
                {
                    Debug.WriteLine("Combination: "+ ++idx);

                    for (int j = 0; j < i; j++)
                    {
                        Debug.WriteLine(productItem.employeesPartition[j].ToArrayString() + " : " + permutationOfJobs.ToArray()[j].ToArrayString());
                    }
                }
            }
        }

输出：

Partition to 1 parts:
Combination: 1
{ Adam , Bob } : { 1 , 2 , 3 }
Partition to 2 parts:
Combination: 1
{ Bob } : { 2 , 3 }
{ Adam } : { 1 }
Combination: 2
{ Bob } : { 1 }
{ Adam } : { 2 , 3 }
Combination: 3
{ Bob } : { 1 , 3 }
{ Adam } : { 2 }
Combination: 4
{ Bob } : { 2 }
{ Adam } : { 1 , 3 }
Combination: 5
{ Bob } : { 3 }
{ Adam } : { 1 , 2 }
Combination: 6
{ Bob } : { 1 , 2 }
{ Adam } : { 3 }

只需计算结果，我们就可以轻松检查我们的输出。
在这个例子中，我们有一组 2 个元素，一组 3 个元素，等式 2 表明我们需要 S(2,1)S(3,1)1!+S(2,2)S(3,2 )2！= 1+6 = 7
这正是我们得到的组合数。

作为参考，这里是第二类斯特林数的例子：
S(1,1) = 1

S(2,1) = 1
S(2,2) = 1

S(3,1) = 1
S(3,2) = 3
S(3,3) = 1

S(4,1) = 1
S(4,2) = 7
S(4,3) = 6
S(4,4) = 1

2012 年 6 月 19 日编辑

public static String ToArrayString<T>(this IEnumerable<T> arr)
    {
        string str = "{ ";

        foreach (var item in arr)
        {
            str += item + " , ";
        }

        str = str.Trim().TrimEnd(',');
        str += "}";

        return str;
    }

2012 年 6 月 24 日编辑

这个算法的主要部分是找到斯特林集，我使用了一种低效的排列方法，这是一个基于 QuickPerm 算法的更快的方法：

public static IEnumerable<IEnumerable<T>> QuickPerm<T>(this IEnumerable<T> set)
    {
        int N = set.Count();
        int[] a = new int[N];
        int[] p = new int[N];

        var yieldRet = new T[N];

        var list = set.ToList();

        int i, j, tmp ;// Upper Index i; Lower Index j
        T tmp2;

        for (i = 0; i < N; i++)
        {
            // initialize arrays; a[N] can be any type
            a[i] = i + 1; // a[i] value is not revealed and can be arbitrary
            p[i] = 0; // p[i] == i controls iteration and index boundaries for i
        }
        yield return list;
        //display(a, 0, 0);   // remove comment to display array a[]
        i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
        while (i < N)
        {
            if (p[i] < i)
            {
                j = i%2*p[i]; // IF i is odd then j = p[i] otherwise j = 0

                tmp2 = list[a[j]-1];
                list[a[j]-1] = list[a[i]-1];
                list[a[i]-1] = tmp2;

                tmp = a[j]; // swap(a[j], a[i])
                a[j] = a[i];
                a[i] = tmp;

                //MAIN!

               // for (int x = 0; x < N; x++)
                //{
                //    yieldRet[x] = list[a[x]-1];
                //}
                yield return list;
                //display(a, j, i); // remove comment to display target array a[]

                // MAIN!

                p[i]++; // increase index "weight" for i by one
                i = 1; // reset index i to 1 (assumed)
            }
            else
            {
                // otherwise p[i] == i
                p[i] = 0; // reset p[i] to zero
                i++; // set new index value for i (increase by one)
            } // if (p[i] < i)
        } // while(i < N)
    }

这将把时间减少一半。
但是，大部分 CPU 周期都用于字符串构建，这是本示例特别需要的。
这将使它更快一点：

             results.Add(productItem.employeesPartition[j].Aggregate((a, b) => a + "," + b) + " : " + permutationOfJobs.ToArray()[j].Aggregate((a, b) => a + "," + b));

在 x64 中编译会更好，因为这些字符串占用大量内存。

Answer 2

在我的回答中，我将忽略您最后的结果： Adam, Bob: 1, 2, 3，因为它在逻辑上是一个例外。跳到最后查看我的输出。

解释：

这个想法是迭代“元素属于哪个组”的组合。

假设您有元素“a, b, c”，并且有组“1, 2”，让我们有一个大小为 3 的数组作为元素数，它将包含组“1, 2”的所有可能组合，重复：

{1, 1, 1} {1, 1, 2} {1, 2, 1} {1, 2, 2}
{2, 1, 1} {2, 1, 2} {2, 2, 1} {2, 2, 2}

现在我们将采用每个组，并通过以下逻辑从中创建一个键值集合：

的组elements[i]将是 的值comb[i]。

Example with {1, 2, 1}:
a: group 1
b: group 2
c: group 1

And in a different view, the way you wanted it:
group 1: a, c
group 2: b

毕竟，您只需过滤不包含所有组的所有组合，因为您希望所有组都至少有一个值。

因此，您应该检查所有组是否都以某种组合出现，并过滤掉不匹配的组，这样您将得到：

{1, 1, 2} {1, 2, 1} {1, 2, 2}
{2, 1, 2} {2, 2, 1} {2, 1, 1}

这将导致：

1: a, b
2: c

1: a, c
2: b

1: a
2: b, c

1: b
2: a, c

1: c
2: a, b

1: b, c
2: a

这种打破分组的组合逻辑也适用于更多的元素和组。这是我的实现，可能可以做得更好，因为即使我在编码时也有点迷失了（这确实不是一个直观的问题呵呵），但它效果很好。

执行：

public static IEnumerable<ILookup<TValue, TKey>> Group<TKey, TValue>
    (List<TValue> keys,
     List<TKey> values,
     bool allowEmptyGroups = false)
{
    var indices = new int[values.Count];
    var maxIndex = values.Count - 1;
    var nextIndex = maxIndex;
    indices[maxIndex] = -1;

    while (nextIndex >= 0)
    {
        indices[nextIndex]++;

        if (indices[nextIndex] == keys.Count)
        {
            indices[nextIndex] = 0;
            nextIndex--;
            continue;
        }

        nextIndex = maxIndex;

        if (!allowEmptyGroups && indices.Distinct().Count() != keys.Count)
        {
            continue;
        }

        yield return indices.Select((keyIndex, valueIndex) =>
                                    new
                                        {
                                            Key = keys[keyIndex],
                                            Value = values[valueIndex]
                                        })
            .OrderBy(x => x.Key)
            .ToLookup(x => x.Key, x => x.Value);
    }
}

用法：

var employees = new List<string>() { "Adam", "Bob"};
var jobs      = new List<string>() { "1", "2", "3"};
var c = 0;

foreach (var group in CombinationsEx.Group(employees, jobs))
{
    foreach (var sub in group)
    {
        Console.WriteLine(sub.Key + ": " + string.Join(", ", sub));
    }

    c++;
    Console.WriteLine();
}

Console.WriteLine(c + " combinations.");

输出：

Adam: 1, 2
Bob: 3

Adam: 1, 3
Bob: 2

Adam: 1
Bob: 2, 3

Adam: 2, 3
Bob: 1

Adam: 2
Bob: 1, 3

Adam: 3
Bob: 1, 2

6 combinations.

更新

组合键组合原型：

public static IEnumerable<ILookup<TKey[], TValue>> GroupCombined<TKey, TValue>
    (List<TKey> keys,
     List<TValue> values)
{
    // foreach (int i in Enumerable.Range(1, keys.Count))
    for (var i = 1; i <= keys.Count; i++)
    {
        foreach (var lookup in Group(Enumerable.Range(0, i).ToList(), keys))
        {
            foreach (var lookup1 in
                     Group(lookup.Select(keysComb => keysComb.ToArray()).ToList(),
                           values))
            {
                yield return lookup1;
            }
        }
    }

    /*
    Same functionality:

    return from i in Enumerable.Range(1, keys.Count)
           from lookup in Group(Enumerable.Range(0, i).ToList(), keys)
           from lookup1 in Group(lookup.Select(keysComb =>
                                     keysComb.ToArray()).ToList(),
                                 values)
           select lookup1;
    */
}

仍然存在一些重复的问题，但它会产生所有结果。

这是我用来删除重复项的临时解决方案：

var c = 0;
var d = 0;

var employees = new List<string> { "Adam", "Bob", "James" };
var jobs = new List<string> {"1", "2"};

var prevStrs = new List<string>();

foreach (var group in CombinationsEx.GroupCombined(employees, jobs))
{
    var currStr = string.Join(Environment.NewLine,
                              group.Select(sub =>
                                           string.Format("{0}: {1}",
                                               string.Join(", ", sub.Key),
                                               string.Join(", ", sub))));

    if (prevStrs.Contains(currStr))
    {
        d++;
        continue;
    }

    prevStrs.Add(currStr);

    Console.WriteLine(currStr);
    Console.WriteLine();
    c++;
}

Console.WriteLine(c + " combinations.");
Console.WriteLine(d + " duplicates.");

输出：

Adam, Bob, James: 1, 2

Adam, Bob: 1
James: 2

James: 1
Adam, Bob: 2

Adam, James: 1
Bob: 2

Bob: 1
Adam, James: 2

Adam: 1
Bob, James: 2

Bob, James: 1
Adam: 2

7 combinations.
6 duplicates.

请注意，它还将生成非组合组（如果可能 - 因为不允许空组）。要仅生成组合密钥，您需要替换它：

for (var i = 1; i <= keys.Count; i++)

有了这个：

for (var i = 1; i < keys.Count; i++)

在 GroupCombined 方法的开头。使用三名员工和三份工作来测试该方法，看看它是如何工作的。

另一个编辑：

更好的重复处理是在 GroupCombined 级别处理重复的组合键：

public static IEnumerable<ILookup<TKey[], TValue>> GroupCombined<TKey, TValue>
    (List<TKey> keys,
     List<TValue> values)
{
    for (var i = 1; i <= keys.Count; i++)
    {
        var prevs = new List<TKey[][]>();

        foreach (var lookup in Group(Enumerable.Range(0, i).ToList(), keys))
        {
            var found = false;
            var curr = lookup.Select(sub => sub.OrderBy(k => k).ToArray())
                .OrderBy(arr => arr.FirstOrDefault()).ToArray();

            foreach (var prev in prevs.Where(prev => prev.Length == curr.Length))
            {
                var isDuplicate = true;

                for (var x = 0; x < prev.Length; x++)
                {
                    var currSub = curr[x];
                    var prevSub = prev[x];

                    if (currSub.Length != prevSub.Length ||
                        !currSub.SequenceEqual(prevSub))
                    {
                        isDuplicate = false;
                        break;
                    }
                }

                if (isDuplicate)
                {
                    found = true;
                    break;
                }
            }

            if (found)
            {
                continue;
            }

            prevs.Add(curr);

            foreach (var group in
                     Group(lookup.Select(keysComb => keysComb.ToArray()).ToList(),
                           values))
            {
                yield return group;
            }
        }
    }
}

看起来，向该方法添加约束是明智的做法，以便也可能TKey是。ICompareable<TKey>IEquatable<TKey>

最终结果是 0 个重复项。