c# - 您如何按照从最少到最多非零元素的顺序遍历排列？

Question

我正在尝试编写一个 C# 函数，给定一个像 new int[] { 2, 3, 2 } 这样的参数它为每个元素指定上限 + 1，将返回以下内容(通过 IEnumberable<int[]> ):

0 0 0
0 0 1
0 1 0
0 2 0
1 0 0
0 1 1
0 2 1
1 0 1
1 1 0
1 2 0
1 1 1
1 2 1

请注意顺序很重要:所有具有 0 个非零元素的排列，然后是所有具有 1 个非零元素的排列，等等。在其中一组中，顺序无关紧要。

我意识到这些在技术上可能不是排列，但这是我所知道的最接近的术语。我还意识到，一种方法是按某种顺序返回所有排列，然后根据计算有多少非零元素的函数对它们进行排序，但我希望有更优雅和高效的方法。

Answer 1

我想要一个不先计算所有内容然后排序的答案，同时仍然只处理最少的次数。这就是我所拥有的。请注意，从外部修改 int[] 可能会搞砸结果(或者，可能会返回一个 new int[])。

第一个方法告诉辅助方法它希望在输出中有多少个 0。然后，助手会计算结果，如果无法填充足够多的 0 或遍历所有数据，则会停止。

static IEnumerable<int[]> Permutation(int[] bounds)
{
  for(int num0s = bounds.Length; num0s >= 0; --num0s)
  {
    foreach(int[] ret in PermHelper(num0s, 0, bounds, new int[bounds.Length]))
      yield return ret;
  }
}

static IEnumerable<int[]> PermHelper(int num0s, int index, int[] bounds, int[] result)
{
  //Last index.
  if(index == bounds.Length - 1)
  {
    if(num0s > 0)
    {
      result[index] = 0;
      yield return result;
    }
    else
    {
      for(int i = 1; i < bounds[index]; ++i)
      {
        result[index] = i;
        yield return result;
      }
    }
  }
  //Others.
  else
  {
    //still need more 0s.
    if(num0s > 0)
    {
      result[index] = 0;
      foreach(int[] perm in PermHelper(num0s - 1, index + 1, bounds, result))
        yield return perm;
    }
    //Make sure there are enough 0s left if this one isn't a 0.
    if(num0s < bounds.Length - index)
    {
      for(int i = 1; i < bounds[index]; ++i)
      {
        result[index] = i;
        foreach(int[] perm in PermHelper(num0s, index + 1, bounds, result))
          yield return perm;
      }
    }
  }
}