C# diviser une liste dans toutes les combinaisons de n groupes - migration de code à partir de Python

Question

Il y a une grande implémentation de l'algorithme que je suis après here (par @lazy dog). Cependant, j'ai besoin de cela en C# et la conversion n'est pas triviale en raison de l'absence de C# de yield from et peut-être ma propre tête d'âne.

Voici ce que j'ai actuellement:

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 
} 

Quelqu'un peut-il voir des erreurs évidentes, je suis sûr que mon manque de compréhension des yield from et les coroutines de Python me fait mal ici.

Edit: Trouvé le bug, a ajouté des commentaires ci-dessus

Answer 1

Quel comportement avez-vous ici?

À mon avis, yield return generate_partitions(i + 1); à la place de la boucle foreach devrait fonctionner correctement. Il suffit d'appeler le récursif de fonction avec la nouvelle valeur i+1

Answer 2

Ok, donc une bonne solution de travail, je suis venu avec ici:

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

C'est un peu plus rapide que python que vous attendez, mais encore pas génial. J'ai expérimenté la parallélisation mais je ne suis pas allé trop loin. J'ai aussi expérimenté en essayant de supprimer certaines créations d'objets et en utilisant Array.Copy à la place. Le désordre créé ne valait pas les améliorations de performance négligeables. Je suppose que c'est juste lent car à mesure que les nombres grossissent (disons 15 à 20 éléments), le nombre de combinaisons est tout simplement énorme et aucune optimisation ne peut aider à en faire un problème plus facile à résoudre.