4

我正在尝试编写一个 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 个非零元素的排列，等等。在这些组之一中，顺序无关紧要。

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

4

2 回答 2

1

如果此代码存在语法错误（无法测试），我深表歉意，但希望您能理解。

IEnumerable<int[]> Permutations(int[] upperBounds) {
    int[] c = new int[upperBounds.Length] {};

    while(true) {
        int i = c.Length - 1;

        while(i >= 0 && c[i] == upperBounds[i]) {
            c[i] = 0;
            i--;
        }

        if(i == -1) break;

        c[i]++;

        yield return (int[]) c.Clone();
    }
}

如果您使用回调并保持相同的数组引用，它会变得更好，但您要求一个IEnumerable. 如果Clone可以不使用，请务必使用它 - 它会更有效率。

于 2012-05-18T23:53:53.930 回答
1

我想要一个不先计算所有内容然后排序的答案，同时仍然只通过最少的时间处理事情。这就是我所拥有的。请注意，从外部修改int[]可能会搞砸结果（或者，可能会返回 a 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;
      }
    }
  }
}
于 2012-05-25T23:57:26.513 回答