C＃将一个列表分成n组的所有组合 - 从Python迁移代码

在here（由@lazy dog）之后，我有一个很好的算法实现。然而，我需要这个在C＃中，并且由于C＃缺少yield from以及可能是我自己的粗心，转换不是微不足道的。C＃将一个列表分成n组的所有组合 - 从Python迁移代码

这是我目前有：

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的yield from和协同程序的理解在这里伤害我。

编辑：发现该错误，在上面添加评论

来源

2017-09-26 gatapia

你在这里得到什么行为？

在我看来yield return generate_partitions(i + 1);而不是foreach循环应该可以正常工作。它只是将调用该函数的递归与新价值i+1

来源

2017-09-26 07:42:08 TheSkimek

没有'yield return generate_partitions（i + 1）'试图产生一个'IEnumerable '，我只需要产生一个'ArrayList'。我非常肯定，python的'generate_partitions'产出与'foreach（generate_particions中的var d）yield return d'非常相似。然而，在这种情况下，天真的类似的不错的enuf。 – gatapia

确定这样一个良好的工作解决方案，我想出了是在这里：

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个项目的序列），那么组合的数量是巨大的，没有优化可以帮助将它变成更容易处理的问题。

来源

2017-09-26 20:46:18 gatapia

C＃将一个列表分成n组的所有组合 - 从Python迁移代码

回答

相关问题