c# – 检索两个列表的每个可能的子列表组合的算法

概述假设我有两个列表,如何遍历每个子列表的每个可能组合,这样每个项目只出现一次. 我想一个例子可能是你有员工和工作,你想把他们分成团队,每个员工只能在一个团队中,每个工作只能在一个团队中.例如 List<string> employees = new List<string>() { "Adam", "Bob"} ;List<string> jobs = new List<string> 假设我有两个列表,如何遍历每个子列表的每个可能组合,这样每个项目只出现一次.

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

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

我想要

Adam       : 1Bob        : 2,3Adam       : 1,2Bob        : 3Adam       : 1,3Bob        : 2Adam       : 2 Bob        : 1,3Adam       : 2,3Bob        : 1Adam       : 3Bob        : 1,2Adam,Bob  : 1,2,3

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

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

更新

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

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

var employees = new List<string>() { "Adam","Bob"  } ;var jobs      = new List<string>() { "1","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));

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

解决方法 在我的回答中,我将忽略你最后的结果：亚当,鲍勃：1,3,因为它在逻辑上是一个例外.跳到最后查看我的输出.

说明：

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

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

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

现在我们将采用每个组,并使用以下逻辑从中进行键值集合：

元素组[i]将是comb [i]的值.

Example with {1,1}:a: group 1b: group 2c: group 1And in a different vIEw,the way you wanted it:group 1: a,cgroup 2: b

毕竟,您只需要过滤掉所有不包含所有组的组合,因为您希望所有组至少有一个值.

因此,您应检查所有组是否以特定组合显示并过滤掉不匹配的组,因此您将留下：

{1,1}

这将导致：

1: a,b2: c1: a,c2: b1: a2: b,c1: b2: a,c1: c2: a,b1: b,c2: 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","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,2Bob: 3Adam: 1,3Bob: 2Adam: 1Bob: 2,3Adam: 2,3Bob: 1Adam: 2Bob: 1,3Adam: 3Bob: 1,26 combinations.

UPDATE

组合键组合原型：

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,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),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,Bob: 1James: 2James: 1Adam,Bob: 2Adam,James: 1Bob: 2Bob: 1Adam,James: 2Adam: 1Bob,James: 2Bob,James: 1Adam: 27 combinations.6 duplicates.

请注意,它还将生成非组合组(如果可能 – 因为不允许空组).要生成ONLY组合键,您需要替换它：

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

有了这个：

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

在GroupCombined方法的开头.用三名员工和三份工作来测试方法,看看它是如何工作的.

另一个编辑：

更好的重复处理将处理GroupCombined级别中的重复键组合：

public static IEnumerable<ILookup<TKey[],List<TValue> values){    for (var i = 1; i <= keys.Count; i++)    {        var prevs = new List<TKey[][]>();        foreach (var lookup in Group(Enumerable.Range(0,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个重复.

总结

以上是内存溢出为你收集整理的c# – 检索两个列表的每个可能的子列表组合的算法全部内容，希望文章能够帮你解决c# – 检索两个列表的每个可能的子列表组合的算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。