C # broke the list into all combinations of n groups - code transition from Python

Question

There is a big implementation of the algorithm that I am after here ( @lazy dog) . However, I need this in C #, and the conversion is not trivial due to the lack of C # yield from and possibly my own thickness.

Here is what I have now:

 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 } 

Can anyone see any obvious errors, I'm sure my lack of understanding of Python yield from and coroutines hurt me.

Edit: error found, comments added above

Answer 1

Ok, so the good working solution I came up with is here:

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

This is slightly faster than python, as you expected, but still not very. I experimented with parallelization, but did not go too far. I also experimented trying to remove some of the object creations and using Array.Copy instead. The mess created was not worth the slightest performance improvements. I think it’s just slow, because when the numbers get bigger (say, from 15 to 20 pieces), the number of combinations is just huge, and no optimizations can help make this a more difficult problem.

Answer 2

What kind of behavior are you getting here?

In my opinion yield return generate_partitions(i + 1); instead of a foreach loop should work fine. It will just call the recursive function with the new value i+1