Algoritmul de recuperare a tuturor combinațiilor posibile de subliste de două liste

Să presupunem că am două liste, cum pot itera prin fiecare combinație posibilă a fiecărei sublistări, astfel încât fiecare element să apară o singură dată.

Cred că un exemplu ar putea fi dacă aveți angajați și locuri de muncă și doriți să le împărțiți în echipe, unde fiecare angajat poate fi doar într-o echipă și fiecare loc de muncă poate fi într-o singură echipă. De exemplu

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

eu vreau

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

Am încercat să folosesc răspunsul la această întrebare stackoverflow pentru a genera o lista tuturor combinațiilor posibile de angajați și a oricărei combinații posibile de locuri de muncă și apoi selectați câte un element din fiecare din fiecare listă, dar este cam la fel de mult ca mine.

Nu cunosc dimensiunea maximă a listelor, dar ar fi cu siguranță mai mică de 100 și pot exista și alți factori limitativi (cum ar fi fiecare echipă să nu aibă mai mult de 5 angajați)

Actualizare

Nu sunt sigur dacă acest lucru poate fi mai bine și/sau simplificat, dar cu toate acestea am ajuns până acum.

Utilizează algoritmul grupului furnizat de Yorye (a se vedea răspunsul său de mai jos), dar am eliminat comanda prin care nu am nevoie și am cauzat probleme dacă cheile nu sunt comparabile.

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

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

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

Din moment ce nu sunt îngrijorat de ordinea rezultatelor, acest lucru mi se pare că îmi dă ce am nevoie.

0
@YoryeNathan. Nu. Acest lucru ar trebui să citească "fiecare echipă trebuie să aibă cel puțin un angajat și un loc de muncă". Cu alte cuvinte, fiecare angajat trebuie să aibă ceva de făcut și fiecare loc de muncă trebuie să aibă pe cineva să o facă.
adăugat autor sgmoore, sursa
@mbeckish. Da, fiecare echipă trebuie să aibă cel puțin un singur angajat și un loc de muncă.
adăugat autor sgmoore, sursa
@Douglas, Da, acestea sunt rezultate valide. Voi edita întrebarea.
adăugat autor sgmoore, sursa
Pot obține un loc de muncă doi angajați?
adăugat autor Rafael Baptista, sursa
Presupun că și tu vrei Adam: 2; Bob: 1, 3 și Adam: 3; Bob: 1, 2 ?
adăugat autor Douglas, sursa
Există restricții, cum ar fi ca fiecare echipă să primească un minim de 1 loc de muncă?
adăugat autor mbeckish, sursa
@sgmoore Dar acum ești doar confuză din nou. Vrei să spui că fiecare linie ar trebui să aibă exact un angajat și cel puțin un loc de muncă?
adăugat autor SimpleVar, sursa

5 răspunsuri

V-ați putea folosi o altă bibliotecă? Aici este o bibliotecă generică pentru combinații în mod evident vreau una fără repetare). Apoi, va trebui doar să faceți o foreach peste lista dvs. de angajați și să executați combinația w/ambele.

Nu cred că îți faci niște favoruri dintr-o perspectivă O mare, e eficiența o prioritate aici?

Aceasta este de la șold, dar acesta ar trebui să fie codul pentru a obține ceea ce doriți (cu biblioteca respectivă):

Combinations combinations = new Combinations(jobs, 2);

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

Apoi, acest lucru ar trebui să fie aplicat fiecărui angajat

0
adăugat
new Combinations (joburi, 2); va genera combinatii de jobs fiecare cu mărimea 2 sau mai mare, NU va genera toate combinațiile de combinații, combinațiile sunt egale cu 2. Veți obține numai {1,2} {1,3} {2,3} - acum ce?
adăugat autor SimpleVar, sursa

Say we have two sets, A and B.
A = {a1, a2, a3} ; B = {b1, b2, b3}

Mai întâi, să luăm un set format din tupluri care conțin un subset și complementul său:

{a1} {a2 a3} 
{a2} {a1 a3}
{a3} {a1 a2}
{a2, a3} {a1}
...

Pentru aceasta, puteți folosi biblioteca lui Rikon de mai sus sau puteți scrie propriul cod. Va trebui să faceți acest lucru:

  1. Obțineți un set de toate subseturile (cunoscut ca setul de putere)
  2. Pentru fiecare subset, obțineți complementul sau elementele rămase ale subsetului respectiv din setul mai mare.
  3. Alăturați-vă într-un tuplu sau pereche; de exemplu. (subset, complement)

Ordinea contează aici; {a1} {a2 a3} și {a2 a3} {a1} sunt tupluri diferite, la urma urmei.

Apoi vom obține un set similar pentru B. Apoi, vom efectua un cross join între cele două seturi, pentru a obține:

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

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

Acest lucru corespunde destul de mult descrierii de mai sus. Priviți {Bob, Adam} ca un set și {1, 2, 3} ca un alt set. Va trebui să aruncați câteva seturi goale (deoarece un set de putere include și subseturi goale), în funcție de cerințele dvs. Acesta este, însă, totul, în măsura în care pot spune. Ne pare rău pentru lipsa codului; Trebuie să dorm: P

0
adăugat
Pot să înțeleg cum funcționează acest lucru dacă numărul de echipe este doar două. (Sunt doar două în exemplul meu, deoarece sunt doar doi angajați). În exemplul dvs. nu numai că trebuie să iau în considerare {a1} {a2 a3}, dar întotdeauna {a1} {a2} {a3}. Cred că acest lucru va implica recursivitate, dar asta e locul în care mi se pare că merg în cercuri?
adăugat autor sgmoore, sursa

Dacă ignorați celelalte constrângeri (cum ar fi dimensiunea maximă a echipei), ceea ce faceți este să creați o partiție din setul P și o partiție din setul Q cu același număr de submulțimi , apoi găsirea tuturor combinațiilor unuia dintre seturi pentru a cartografia prima partiție la al doilea.

Lucrarea lui Michael Orlov are ceea ce pare a fi un algoritm simplu pentru generarea de partiții în care fiecare iterație folosește un spațiu constant în această lucrare . De asemenea, el oferă un algoritm pentru listarea partițiilor de o anumită dimensiune.

Începeți cu P = {A, B} și Q = {1, 2, 3} </și [Q] , astfel încât singura împerechere este ([P], [Q])

Pentru partițiile de mărimea 2, P are doar două elemente, deci doar o partiție de dimensiune 2 [{A}, {B}] are trei partiții de mărimea 2 [{1}, {2, 3}], [{1, 2}, {3}], [{1, 3}, 2} .

Deoarece fiecare partiție a Q conține două subseturi, există 2 combinații ale fiecărei partiții, care vă oferă șase perechi:

( [ { 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 } ] ) 

Deoarece mărimea unuia dintre seturile originale era de 2, nu există partiții de mărimea 3 din ea, așa că ne oprim.

0
adăugat

In my answer I will ignore the last result you had: Adam, Bob: 1, 2, 3, because it is an exception logically. Skip to the end to see my output.

Explicație:

Ideea ar fi iterarea combinațiilor de "la care grup va fi un element".

Spuneți că aveți elemente "a, b, c" și aveți grupuri "1, 2", permite să aveți o matrice de dimensiune 3, ca număr de elemente care vor conține toate combinațiile posibile ale grupurilor "1, 2" , Cu repetiție:

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

Acum vom lua fiecare grup și vom face dintr-o colecție de valori cheie, cu următoarea logică:

Grupul de elements [i] va fi valoarea 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

După toate acestea, trebuie să filtrați toate combinațiile care nu conțin toate grupurile, deoarece doriți ca toate grupurile să aibă cel puțin o valoare.

Deci, ar trebui să verificați dacă toate grupurile apar într-o anumită combinație și să filtrați cele care nu se potrivesc, astfel încât veți rămâne cu:

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

Care va avea ca rezultat:

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

Această logică de combinație de grup va funcționa pentru o cantitate mai mare de elemente și grupuri. Iată implementarea mea, care poate fi făcută mai bine, pentru că chiar m-am pierdut puțin în timp ce l-am codificat (nu este o problemă intuitivă hehe), dar funcționează bine.

Punerea în aplicare:

public static IEnumerable> Group
    (List keys,
     List 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);
    }
}

Utilizare:

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

Ieșire:

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

Combinații chei combinații prototip:

public static IEnumerable> GroupCombined
    (List keys,
     List 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;
    */
}

Există încă o mică problemă de duplicate, dar produce toate rezultatele.

Iată ce aș folosi pentru a elimina duplicatele , ca o soluție temporară :

var c = 0;
var d = 0;

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

var prevStrs = new List();

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

Ieșire:

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 that it will also produce non-combined groups (if possible - because no empty groups are allowed). To produce ONLY combined-keys you will need to replace this:

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

Cu asta:

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

La începutul metodei GroupCombined. Testați metoda cu trei angajați și trei locuri de muncă pentru a vedea cum funcționează exact.

ALTĂ EDITARE:

O mai bună manipulare a duplicatelor va fi manipularea combinațiilor de chei duplicate la nivelul GroupCombined:

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

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

As it seems, it would be smart to add constraints to the method so that TKey will be ICompareable and maybe also IEquatable.

Rezultatul este cu 0 duplicate în cele din urmă.

0
adăugat
Nu am dat seama ce, dar trebuie să existe o eroare cu ultima ta schimbare, deoarece nu produce același număr de rezultate ca și versiunea anterioară, ceea ce sunt destul de sigur că a fost corectă. Dacă încercați patru angajați și trei locuri de muncă obțineți 55 de rezultate, în timp ce cred că ar trebui să obțineți 79. Vestea mărfurilor este că am integrat răspunsul dvs. anterior (adică cel pe care l-am adăugat la întrebarea mea) în codul meu și testat într-unul date și produce rezultatele pe care le aștept și în timp rezonabil. Deci, dacă vreți să schimbați răspunsul înapoi, îl voi marca dr
adăugat autor sgmoore, sursa
Doar noua versiune a rutinei GroupCombined.
adăugat autor sgmoore, sursa
Versiunea dvs. este mult mai ușor de citit (și cred că voi fura un alt fragment al codului dvs.). Dar, deoarece elimină duplicatele după , toate combinațiile sunt calculate, este mult mai lent pentru seturile mai mari. De exemplu, o matrice de 5 x 7 produce 4,306,681 combinații și apoi aruncă 96% din ele. (De asemenea, atunci când ajungi la acel număr de elemente, HashSet este mult mai rapid decât lista )
adăugat autor sgmoore, sursa
Da, cel care vă răspunde în prezent.
adăugat autor sgmoore, sursa
Doar o actualizare. Mi-am modificat întrebarea pentru a include un posibil răspuns bazat pe algoritmul dvs. de grup. Încă mai aveți câteva teste pentru a alerga și, dacă trec, atunci vă pot marca răspunsul dvs. ca fiind unul acceptat.
adăugat autor sgmoore, sursa
Consultați pastebin.com/S44UXnLT . Aceasta conține atât versiunile vechi, cât și cele noi ale metodelor dvs. GroupCombined și dacă le schimbați, veți vedea că NewGroupCombined oferă 55 de rezultate, în timp ce OldGroupCombined dă 79, care este corect.
adăugat autor sgmoore, sursa
Încerc să aflu exact ce face această rutină, dar dacă încercați să apelați GroupCombined cu trei angajați, aceasta va întoarce tot felul de rezultate ciudate.
adăugat autor sgmoore, sursa
Pe scurt, aș spune că îți apreciez eforturile și cred că asta ma apropiat de locul în care trebuie să fiu. Cu toate acestea, dacă adăugați Charlie la lista de angajați, algoritmul dvs. nu dă rezultate, cum ar fi Adam, Bob care lucrează la Locuri de muncă 1 și 2, iar Charlie lucrează la 3. I cred că din toate acestea, produceți o listă a tuturor combinațiilor posibile de echipe și apoi alocați locurile de muncă fiecărei echipe folosind metoda dvs. de grup, ceea ce încerc acum să fac.
adăugat autor sgmoore, sursa
@sgmoore Mă bucur că a funcționat în cele din urmă! Vă referiți la prima mea bucată de cod văzută în răspunsul meu sau în grupul combinat din ultima versiune?
adăugat autor SimpleVar, sursa
Se calculează numai grupul de combinații actual în fiecare iterație, dar da, hashset-ul ar fi mai rapid. Punctul a fost, în principal, acela de a "compara" cu datele anterioare în formă de șir care este necesar oricum, în loc de tablouri și liste de combinații chei și valori etc. Altele decât - întregul algoritm nu este prea bun pentru numere mari - pentru că duplicatele vor fi acolo oriunde, ceea ce ne-ar plăcea să evităm. Ce putem face este să manipulăm duplicatele la un nivel inferior. Vedeți editarea mea.
adăugat autor SimpleVar, sursa
@sgmoore Cel în prezent în răspuns?
adăugat autor SimpleVar, sursa
@sgmoore Am revizuit actualizarea dvs. și m-am gândit, de asemenea, să verific doar pentru duplicate și să le ignor, dar într-adevăr nu este soluția perfectă. Sunt doar câteva lucruri combinotorice pe care nu le-am dat seama încă liniștit. Dar, desigur, ignorarea duplicatelor va funcționa foarte bine. Vedeți exemplul meu pentru cum aș ignora duplicatele (mai ușor de citit, cred).
adăugat autor SimpleVar, sursa
Nu urmăresc. Ați spus că o versiune mai veche a funcționat și cea care se află în prezent în răspuns nu. Puteți să pastebin versiunea de lucru și diferențele dintre rezultatele din răspunsul?
adăugat autor SimpleVar, sursa
@sgmoore Ai dreptate, am editat acea parte. Ideea generală de a face ceea ce doriți în continuare, folosește grupul cu listă falsă ca chei și chei reale ca valori. Lista manechinului vă va lăsa să indice în combinația de taste. Apoi aveți toate combinațiile de chei, fiecare grup de combinații fiind cheile cu valorile reale. Este cam greu să explici (și să urmezi).
adăugat autor SimpleVar, sursa
@sgmoore Vedeți actualizarea :) Am făcut o altă metodă de generare a combinațiilor cu chei combinate (cum ar fi Adam, Bob ) și oa treia metodă care le împachetează pe amândouă. Verifică-l și spune-mi cum îți place.
adăugat autor SimpleVar, sursa
@sgmoore Am găsit un bug în noua versiune și l-am fixat (editat). A fost în partea în care mă uit pentru a vedea dacă gruparea cheilor există în prevs . A trebuit să adaugă variabila isDuplicate pentru a testa egalitatea unu-la-unu, iar variabila found indică un general "one-exists-in-many". Noua versiune produce acum 79 de rezultate, precum și 0 duplicate.
adăugat autor SimpleVar, sursa
Și pot adăuga: Vă mulțumim pentru această provocare plăcută! Îmi plac întrebări precum acesta, care mă ocupă și mă dezvoltă și pe mine.
adăugat autor SimpleVar, sursa

Buna intrebare.

Mai întâi înainte de a vă scrie codul în jos, permiteți să înțelegeți combinatorii din întrebarea dvs.

Practic, aveți nevoie de faptul că pentru orice partiție din setul A, aveți nevoie de același număr de piese în setul B.

De exemplu. Dacă împărțiți setul A la 3 grupuri, aveți nevoie de faptul că setul B va fi împărțit și la 3 grupuri, dacă cel puțin un element nu va avea un grup corespunzător în celălalt set. Este mai ușor să o imaginezi cu grupul de divizare A la 1 trebuie să avem un grup făcut din setul B ca în exemplul tău (Adam, Bob: 1, 2, 3).

So now, we know that set A has n elements and that set B has k elements.
So naturally we cannot request that any set be split more that Min(n,k).

Let's say we split both sets to 2 groups (partitions) each, now we have 1*2=2! unique pairs between the two sets.
Another example is 3 groups each would give us 1*2*3=3! unique pairs.

However, we're still not finished, after any set is split into several subsets (groups), we can still order the elements in many combinations.
So for m partitions of a set we need to find how many combinations of placing n elements in m partitions.
This can be found by using the Stirling number of the second kind formula:

(Eq 1) Stirling Number of the Second Kind

This formula gives you The number of ways of partitioning a set of n elements into k nonempty sets.

So the total number of combinations of pairs for all partitions from 1 to min(n,k) is:

(Eq 2) All combinations

In short, it's the sum of all partition combinations of both sets, times all combinations of pairs.

Deci, acum înțelegem cum să partiționăm și să împerecheză datele noastre, putem scrie codul în jos:

Cod:

So basically, if we look at our final equation (2) we understand the we need four parts of code to our solution.
1. A summation (or loop)
2. A way to get our Stirling sets or partitions from both sets
3. A way to get the Cartesian product of both Stirling sets.
4. A way to permutate through the items of a set. (n!)

Pe StackOverflow găsiți numeroase modalități de depunere a obiectelor permuatate și cum să găsiți produse cartesiene, aici este un exemplu (ca metodă de extensie):

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

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

Aceasta a fost partea ușoară a codului Partea mai dificilă (imho) găsește toate partițiile n posibile ale unui set Deci, pentru a rezolva acest lucru, am rezolvat mai întâi cea mai mare problemă a modului de a găsi toate partițiile posibile dintr-un set (nu doar de dimensiunea n).

Am venit cu această funcție recursivă:

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

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

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


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

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

                    x.Add(parts[0]);

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

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

The return value of : List>> just means a List of all possible partitions where a partition is a list of sets and a set is a list of elements.
We do not have to use the type List here, but it simplifies indexing.

So now let's put everything together:

Codul principal

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

Ieșire:

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 }

Putem verifica cu ușurință rezultatele noastre doar prin numărarea rezultatelor În acest exemplu avem un set de 2 elemente și un set de 3 elemente, Ecuația 2 afirmă că avem nevoie de S (2,1) S (3,1) 1 1 + S (2,2) S (3,2 ) 2! = 1 + 6 = 7
care este exact numărul de combinații pe care le avem.

For reference here are examples of Stirling number of the second kind:
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

Editați 19.6.2012

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

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

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

        return str;
    }

Editați 24.6.2012

The main part of this algorithm is finding the Stirling sets, I've used an inneficient Permutation method, here is a faster one based on the QuickPerm algorithm:

public static IEnumerable> QuickPerm(this IEnumerable 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)
    }

This will take cut the time in half.
However, most of the CPU cycles go to string building, which is specifically needed for this example.
This will be a make it a bit faster:

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

Compiling in x64 will be better cause these strings are taking a lot of memory.

0
adăugat
Remediați linia .OrderBy (x => x.Key)
adăugat autor sgmoore, sursa
Mulțumiri. Va dura ceva timp pentru a trece și înțelege acest lucru. Am descarcat codul si produce acelasi numar de rezultate ca si algoritmul meu curent (bazat pe raspunsul lui Yorye). Cu toate acestea, este destul de puțin mai lent (aproape zece ori), iar timpul este un factor foarte important.
adăugat autor sgmoore, sursa
Dacă vrei să te uiți la codul meu de testare la pastebin.com/bF8yNPbA - Din testele mele ar părea că rezultatul dvs. este mai rapid pentru seturile de date mai mici, dar mai lent pentru seturile mai mari.
adăugat autor sgmoore, sursa
Ne pare rău, dar exemplul lui Yorye nu funcționează pentru mine, o excepție excepțională, astfel încât nu pot compara complexitatea lor.
adăugat autor Erez Robinson, sursa
Am făcut niște verificări, soluția mea este mai rapidă, de fapt pentru 6 angajați și 3 locuri de muncă, soluția mea a durat mai puțin de 15ms fără ieșire din consola, iar soluția Yorye a luat 83ms. Verificați algoritmii fără ieșire Consola, deoarece există o mare diferență în Debug.WriteLine și Console.Writeline, iar fluxurile de ieșire au tendința de a interpreta greșit complexitatea algoritmului. Sper că veți fi mulțumit.
adăugat autor Erez Robinson, sursa
În plus, nu am adăugat implementarea mea de "ToArrayString", astfel încât ar fi putut să o implementați diferit.
adăugat autor Erez Robinson, sursa
Da, ai dreptate, dar te rog să te uiți la editarea mea. Utilizați QuickPerm în loc de Permute și schimbați concatenarea șirului la Aggregate. Vă rugăm să înțelegeți că algoritmul meu funcționează pentru toate T, alte algo-uri pentru T = String, și are nevoie de ceva lucru pentru a lucra cu alte T. Dacă nu aveți nevoie de acest șir de ieșire algo-ul meu este destul de rapid, doar comentați concatenarea șir si vezi.
adăugat autor Erez Robinson, sursa
Am optimizat metoda QuickPerm, algoritmul este acum de 3 ori mai rapid! :)
adăugat autor Erez Robinson, sursa