c# - Algorithm to retrieve every possible combination of sublists of a two lists -

suppose have 2 lists, how iterate through every possible combination of every sublist, such each item appears once , once.

i guess example if have employees , jobs , want split them teams, each employee can in 1 team , each job can in 1 team. eg

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 

i tried using answer this stackoverflow question generate list of every possible combination of employees , every possible combination of jobs , select 1 item each each list, that's far got.

i don't know maximum size of lists, less 100 , there may other limiting factors (such each team can have no more 5 employees)

update

not sure whether can tidied more and/or simplified, have ended far.

it uses group algorithm supplied yorye (see answer below), removed orderby don't need , caused problems if keys not comparable.

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 unique key each group 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 {1} employees , {2} jobs" , c , employees.count, jobs.count));   

since i'm not worried order of results, seems give me need.

in answer ignore last result had: adam, bob: 1, 2, 3, because exception logically. skip end see output.

explanation:

the idea iterating combinations of "which group element belong to".

say have elements "a, b, c", , have groups "1, 2", lets have array of size 3, number of elements, contain possible combinations of groups "1, 2", repetition:

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

now shall take each group, , sort of make key-value collection out of it, following logic:

group of elements[i] value of comb[i].

example {1, 2, 1}: a: group 1 b: group 2 c: group 1  , in different view, way wanted it: group 1: a, c group 2: b 

after that, have filter combinations not contain groups, because wanted groups have @ least 1 value.

so should check if groups appear in combination , filter ones don't match, you'll left with:

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

which result in:

1: a, b 2: c  1: a, c 2: b  1: 2: b, c  1: b 2: a, c  1: c 2: a, b  1: b, c 2: 

this group-breaking combination logic work bigger amount of elements , groups well. here implementation, can done better, because got little lost in there while coded (it's not intuitive problem hehe), works good.

implementation:

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

usage:

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

output:

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. 

update

combined keys combinations prototype:

public static ienumerable<ilookup<tkey[], tvalue>> groupcombined<tkey, tvalue>     (list<tkey> keys,      list<tvalue> values) {     // foreach (int in enumerable.range(1, keys.count))     (var = 1; <= 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 in enumerable.range(1, keys.count)            lookup in group(enumerable.range(0, i).tolist(), keys)            lookup1 in group(lookup.select(keyscomb =>                                      keyscomb.toarray()).tolist(),                                  values)            select lookup1;     */ } 

there's still little problem of duplicates, produces results.

here use to remove duplicates, temporary solution:

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

output:

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. 

note produce non-combined groups (if possible - because no empty groups allowed). produce combined-keys need replace this:

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

with this:

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

in beginning of groupcombined method. test method 3 employees , 3 jobs see how works exactly.

another edit:

a better duplicates-handling handling duplicate key-combinations in groupcombined level:

public static ienumerable<ilookup<tkey[], tvalue>> groupcombined<tkey, tvalue>     (list<tkey> keys,      list<tvalue> values) {     (var = 1; <= 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;                  (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;             }         }     } } 

as seems, smart add constraints method tkey icompareable<tkey> , maybe iequatable<tkey>.

this results 0 duplicates in end.