C＃将列表分为n个组的所有组合-从Python迁移代码 [英] C# split a list into all combinations of n groups - code migration from Python

问题描述

我在此处（通过 @lazy dog ） 。但是，我在c＃中需要这样做，由于C＃缺乏 的收益以及可能是我本人的糊涂，因此转换并不容易。

There is a great implementation of the algorithm I am after here (by @lazy dog). However, I need this in c# and the conversion is not trivial due to C#'s lack of yield from and perhaps my own thickheadedness.

这是我目前拥有的东西：

Here is what I currently have:

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
}

谁能看到任何明显的错误，我敢肯定，我对Python的收益缺乏了解，协程在这里伤害了我。

Can anyone see any obvious mistakes, I'm sure my lack of understanding of Python's yield from and coroutines is hurting me here.

编辑：发现该错误，在上面添加注释

Found the bug, added comments above

推荐答案

好因此我想出了一个很好的可行解决方案：

Ok so a good working solution I have come 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);
}

这比python快一点，但您期望的不是。我尝试了并行化，但是并没有太过深入。我还尝试通过删除一些对象创建并使用Array.Copy来进行试验。造成的混乱不值得忽略可忽略的性能改进。我猜这只是缓慢的，因为随着数字的增加（比如说15到20个项目的序列），那么组合的数量就是巨大的，没有任何优化方法可以使之成为一个更容易解决的问题。

This is a bit faster than python as you would expect but still not great. I experimented with parallelisation but did not get too far. I also experimented by trying to remove some of the object creations and using Array.Copy instead. The mess that created was not worth the negligible performance improvements. I guess this is just slow because as numbers get bigger (say seq of 15-20 items) then the number of combinations is just enormous and no optimisations can help to make that into a more tractable problem.

这篇关于C＃将列表分为n个组的所有组合-从Python迁移代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！