C# teilen Sie eine Liste in alle Kombinationen von n Gruppen - Code-Migration von Python

Question

Es gibt eine große Implementierung des Algorithmus Ich bin nach here (von @lazy dog). Allerdings brauche ich das in C# und die Konvertierung ist nicht trivial wegen C# yield from und vielleicht meine eigene Dickköpfigkeit fehlt. Hier

ist, was ich derzeit haben:

public static IEnumerable<ArrayList> sorted_k_partitions(int[] seq, int k) { 
    var n = seq.Length; 
    var groups = new ArrayList(); //a list of lists, currently empty 

    IEnumerable<ArrayList> generate_partitions(int i) { 
    if (i >= n) { 
     // this line was the bug, was not creating a 
     // deep clone of the list of lists 
     // yield return new ArrayList(groups); 
     yield return new ArrayList(groups.ToArray().Select(g => ((List<int>)g).ToList())); 
     // Ugly but that is because we are using ArrayList 
     // Using proper List<List<int>> cleans this up significantly 
    } 
    else { 
     if (n - i > k - groups.Count) 
     foreach (List<int> group in new ArrayList(groups)) { 
      group.Add(seq[i]); 
      // yield from generate_partitions(i + 1); 
      foreach (var d in generate_partitions(i + 1)) { 
      yield return d; 
      } 
      group.RemoveAt(group.Count - 1); 
     } 

     if (groups.Count < k) { 
     groups.Add(new List<int> {seq[i]}); 
     foreach (var d in generate_partitions(i + 1)) { 
      // things start breaking down here, as this yield return 
      // appears to release flow control and we then get the 
      // yield return above. I have debuged this and the python 
      // version and the python version does not do this. Very hard 
      // to explain considering I don't fully understand it myself 
      yield return d; 
     } 
     groups.RemoveAt(groups.Count - 1); 
     } 
    } 
    } 
    return generate_partitions(0); 
    // don't worry about the sorting methods in the python 
    // version, not needed 
} 

Kann jemand irgendwelche offensichtliche Fehler sehen, ich bin sicher, dass mein Mangel an Verständnis für Python yield from und Koroutinen verletzt mich hier.

Edit: den Fehler gefunden, hinzugefügt Kommentare über

Answer 1

Welches Verhalten bekommen Sie hier?

Meiner Meinung nach yield return generate_partitions(i + 1); anstelle der foreach-Schleife sollte gut funktionieren. Es ruft nur die Funktion rekursiv mit dem neuen Wert i+1

Answer 2

Ok so eine gute Arbeitslösung ich gekommen bin, mit hier oben ist:

public static IEnumerable<List<List<int>>> CreatePartitions(int[] seq, int k) { 
    var n = seq.Length; 
    var groups = new List<List<int>>(); 

    IEnumerable<List<List<int>>> generate_partitions(int i) { 
    if (i >= n) { 
     yield return new List<List<int>>(groups.Select(g => g.ToList())); 
    } 
    else { 
     if (n - i > k - groups.Count) 
     foreach (var group in new List<List<int>>(groups)) { 
      group.Add(seq[i]); 
      foreach (var d in generate_partitions(i + 1)) { 
      yield return d; 
      } 
      group.RemoveAt(group.Count - 1); 
     } 

     if (groups.Count < k) { 
     groups.Add(new List<int> {seq[i]}); 
     foreach (var d in generate_partitions(i + 1)) { 
      yield return d; 
     } 
     groups.RemoveAt(groups.Count - 1); 
     } 
    } 
    } 
    return generate_partitions(0); 
} 

Dies ist ein wenig schneller als Python ist, wie man erwarten würde, aber nach wie vor nicht gut. Ich habe mit Parallelisierung experimentiert, bin aber nicht zu weit gegangen. Ich experimentierte auch, indem ich versuchte, einige der Objekt-Kreationen zu entfernen und stattdessen Array.Copy zu verwenden. Das Chaos, das geschaffen wurde, war die vernachlässigbaren Leistungsverbesserungen nicht wert. Ich denke, das ist nur langsam, denn wenn Zahlen größer werden (sagen wir 15-20 Items), dann ist die Anzahl der Kombinationen einfach enorm und keine Optimierungen können dazu beitragen, dass dies zu einem leichter handhabbaren Problem wird.