4

new int[] { 2, 3, 2 }各要素の上限 + 1 を指定するような引数を指定すると、( 経由でIEnumberable<int[]>)次を返すC# 関数を作成しようとしています。

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 のすべての順列が続きます。これらのグループの 1 つ内では、順序は重要ではありません。

これらは技術的には順列ではないかもしれませんが、私が知っている最も近い用語です。また、すべての順列をある順序で返し、ゼロ以外の要素の数をカウントする関数に従って並べ替える方法があることも理解していますが、よりエレガントで効率的な方法を望んでいます。

4

2 に答える 2

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;
      }
    }
  }
}
于 2012-05-25T23:57:26.513 に答える
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 に答える