检索两个列表的子列表的所有可能组合的算法

6
假设我有两个列表,如何遍历每个子列表的所有可能组合,使得每个项目仅出现一次。
我猜一个例子就像你有员工和工作,你想把他们分成团队,每个员工只能在一个团队中,每个工作也只能在一个团队中。例如:
List<string> employees = new List<string>() { "Adam", "Bob"}  ;
List<string> jobs      = new List<string>() { "1", "2", "3"};

I want

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));  

既然我不关心结果的顺序,这似乎给了我我所需要的。


2
我假设您也想要Adam : 2; Bob: 1, 3Adam : 3; Bob: 1, 2 - Douglas
@Douglas,是的,这些是有效的结果。我将编辑问题。 - sgmoore
@mbeckish。是的,每个团队必须至少有一名员工和一个职位。 - sgmoore
@sgmoore 但是现在你又搞混了。你的意思是每一行应该只有一个员工,至少有一个工作吗? - SimpleVar
@YoryeNathan。不对,应该是“每个团队必须至少有一名员工和一份工作”。换句话说,每个员工都必须有事情做,每份工作都必须有人来完成它。 - sgmoore
显示剩余2条评论
5个回答

5

好问题。

首先,在编写代码之前,让我们了解一下您的问题的基本组合学。

基本上,您要求对于集合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)Stirling Number of the Second Kind

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

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

(方程2)All combinations

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

因此,现在我们了解了如何分区和配对数据,我们可以编写代码:

代码:

因此,如果我们查看最终方程式(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
编辑 19.6.2012
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编译会更好,因为这些字符串占用了大量内存。


谢谢。我需要一些时间来仔细研究和理解这个。我已经下载了代码并且它产生了与我的当前算法相同数量的结果(基于Yorye的答案)。然而,它要慢得多(几乎是十倍),时间是一个非常重要的因素。 - sgmoore
抱歉,但是Yorye的例子对我不起作用,出现了一些IComparable异常,因此我无法比较它们的复杂性。 - Erez Robinson
只需将该行代码注释掉即可: .OrderBy(x => x.Key) - sgmoore
如果您想的话,可以查看我的测试代码:http://pastebin.com/bF8yNPbA - 从我的测试结果来看,您的结果在较小的数据集上更快,但在较大的数据集上则更慢。 - sgmoore
我已经优化了QuickPerm方法,现在算法的速度快了3倍! :) - Erez Robinson
显示剩余3条评论

3
你是否可以考虑使用其他库?这里有一个通用的组合库(显然你需要没有重复的那一种)。然后,你只需要对员工列表进行foreach循环,同时运行组合。

我认为从大O的角度来看,你在效率方面并未得到优化,这里的效率是优先考虑的吗?
这是现成的代码,可以实现你想要的功能(使用该库):
Combinations<string> combinations = new Combinations<string>(jobs, 2);

foreach(IList<string> c in combinations) {
  Console.WriteLine(String.Format("{{{0} {1}}}", c[0], c[1]));
}

然后这需要应用到每一个员工身上。


new Combinations<string>(jobs, 2); 将生成 jobs 中每个大小为 2 或更大的组合,它不会生成所有子组合计数等于 2 的组合。你只会得到 {1,2} {1,3} {2,3} - 然后呢? - SimpleVar

1

在我的回答中,我会忽略你上一次得到的结果:Adam,Bob:1、2、3,因为从逻辑上讲它是一个例外。跳到最后看看我的输出。

说明:

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

假设您有元素“a,b,c”,并且您有组“1,2”,让我们拥有一个大小为3的数组作为元素数量,其中包含所有可能的组合“1,2”,WITH重复:

{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个重复项。


首先,我应该说我非常感谢您的努力,我认为这让我更接近我需要的地方。然而,如果您将Charlie添加到员工列表中,您的算法不会给出Adam、Bob在Jobs 1和2上工作,Charlie在3上工作的结果。我认为这可能通过首先生成所有可能的团队组合,然后使用您的分组方法为每个团队分配工作来解决,这正是我现在正在尝试做的。 - sgmoore
@sgmoore 看看更新 :) 我又写了一个生成组合的方法,可以结合键(例如 Adam, Bob),还有第三个方法将它们包装在一起。看看它,让我知道你喜欢吗。 - SimpleVar
我正在努力弄清楚这个程序在做什么,但如果你尝试用三个员工调用GroupCombined,它会返回各种奇怪的结果。 - sgmoore
@sgmoore 没错,我编辑了那部分。要做下一步想要的事情的一般思路是使用以虚拟列表为键和实际键为值的组。虚拟列表将让您轻松索引到键组合。然后,您就可以获得所有的键组合,每个组合都是具有真实值的键组。这有点难以解释(并且理解)。 - SimpleVar
只是一个更新。我已经编辑了我的问题,根据你们组的算法包括了可能的答案。还需要运行一些测试,如果通过了,我就可以将你们的答案标记为被接受的答案。 - sgmoore
显示剩余12条评论

0
假设我们有两个集合,A 和 B。
A = {a1, a2, a3} ; B = {b1, b2, b3}
首先,让我们得到一个由包含子集和其补集的元组组成的集合:
{a1} {a2 a3} 
{a2} {a1 a3}
{a3} {a1 a2}
{a2, a3} {a1}
...

为此,您可以使用上面提到的Rikon库,或编写自己的代码。您需要执行以下操作:

  1. 获取所有子集(称为幂集)的集合
  2. 对于每个子集,从更大的集合中获取其补集或剩余元素。
  3. 将它们连接成一个元组或一对;例如 (subset, complement)

这里顺序很重要;毕竟 {a1} {a2 a3} 和 {a2 a3} {a1} 是不同的元组。

然后我们为B获取类似的集合。然后,我们在两个集合之间执行交叉连接,以获得:

{a1} {a2 a3} | {b1} {b2 b3}

{a2} {a1 a3} | {b2} {b1 b3}
...

这基本上与您上述的描述相匹配。只需将{Bob,Adam}视为一组,将{1,2,3}视为另一组即可。 根据您的要求,您需要丢弃一些空集(因为幂集还包括空子集)。尽管如此,我认为这是一般的思路。抱歉没有提供代码; 我得去睡觉了:P

如果团队的数量只有两个,我可以理解这个。 (在我的例子中只有两个,因为只有两个员工)。 在你的例子中,我不仅要考虑{a1} {a2 a3},还要考虑{a1} {a2} {a3}。 我猜这将涉及到递归,但那就是我似乎一直在打转的地方? - sgmoore

0

忽略其他限制(例如团队的最大规模),您正在创建集合P和集合Q的一个分区,这些分区具有相同数量的子集,然后找到将第一个分区映射到第二个分区的所有集合的组合。

Michael Orlov的论文中似乎有一个简单的算法,用于生成每次迭代在this paper中使用恒定空间的分区。他还提供了一种列出给定大小的分区的算法。

P = { A, B }Q = { 1, 2, 3 }开始,然后大小为1的分区是[ P ][ Q ],因此唯一的配对是( [ P ], [ Q ] )

对于大小为2的分区,P只有两个元素,因此大小为2的分区只有一个[ { A }, { B } ]Q有三个大小为2的分区[ { 1 }, { 2, 3 } ], [ { 1, 2 }, { 3 } ], [ { 1, 3 }, { 2 } ]
由于每个Q的分区都包含两个子集,因此每个分区有2种组合方式,这给出了6个配对:
( [ { A }, { B } ], [ { 1 }, { 2, 3 } ] )
( [ { A }, { B } ], [ { 2, 3 }, { 1 } ] )
( [ { A }, { B } ], [ { 1, 2 }, { 3 } ] )
( [ { A }, { B } ], [ { 3 }, { 1, 2 } ] )
( [ { A }, { B } ], [ { 1, 3 }, { 2 } ] ) 
( [ { A }, { B } ], [ { 2 }, { 1, 3 } ] ) 

由于原始集合之一的大小为2,因此它没有大小为3的分区,因此我们停止。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接