C#:n個の異なった要素の中から k個を選ぶ順列 #C#

「全ての要素を使った順列を求める」で書いたコードをすこし手直しするだけで、n個の異なった要素の中から k個を選ぶ順列は求まります。

全ての要素を使った順列を求めるコード

public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items) {
    if (items.Count() == 1) {
        yield return new T[] { items.First() };
        yield break;
    }
    foreach (var item in items) {
        var leftside = new T[] { item };
        var unused = items.Except(leftside);
        foreach (var rightside in Enumerate(unused)) {
            yield return leftside.Concat(rightside).ToArray();
        }
    }
}

n個の異なった要素の中からk個を選ぶ順列を求めるコード

上記コードを元に、引数kを追加し、k個を選ぶようにしています。

public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items, int k) {
    if (k == 1) {
        foreach (var item in items) {
            yield return new T[] { item };
        }
        yield break;
    }
    foreach (var item in items) {
        var leftside = new T[] { item };
        var unused = items.Except(leftside);
        foreach (var rightside in Enumerate(unused, k - 1)) {
            yield return leftside.Concat(rightside).ToArray();
        }
    }
}

再帰処理をすることで、kの数が１ずつ減ってゆくわけですが、k が 1になった時は、「itemsから1つを取り出す処理」となりますから、ここだけは特別扱いをしています。それが、

  if (k == 1) {
      foreach (var item in items) {
          yield return new T[] { item };
      }
      yield break;
  }

の箇所です。

重複を許す順列も求めてみる

重複を許す順列は、同じ要素を何回も用いて良い順列です。
引数withRepetitionがtrueの時は重複を許します。これも、既存のコードを少し手直しするだけで求めることができます。
unusedを求めるところで、重複を許す場合は、元のitemsをそのまま利用するようにするだけです。

public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items, int k, bool withRepetition) {
    if (k == 1) {
        foreach (var item in items) {
            yield return new T[] { item };
        }
        yield break;
    }
    foreach (var item in items) {
        var leftside = new T[] { item };
        var unused = withRepetition ? items : items.Except(leftside);
        foreach (var rightside in Enumerate(unused, k - 1, withRepetition)) {
            yield return leftside.Concat(rightside).ToArray();
        }
    }
}

最初の易しい問題の時に、しっかりと問題の本質を理解することが前提だと思いますが、易しい問題から徐々に難しい問題を解いていくようにすれば、意外とすんなりと解けるものですね。

GitHubで最終版のソースコードを公開しています。

重複なしの実行例

  Permutation perm = new Permutation();
  foreach (var n in perm.Enumerate("ABCD", 3)) {
      foreach (var x in n)
          Console.Write("{0} ", x);
      Console.WriteLine();
  }

以下、上記コードを実行した結果です。


A B C
A B D
A C B
A C D
A D B
A D C
B A C
B A D
B C A
B C D
B D A
B D C
C A B
C A D
C B A
C B D
C D A
C D B
D A B
D A C
D B A
D B C
D C A
D C B

重複ありの場合の実行例

    Permutation perm = new Permutation();
    foreach (var n in perm.Enumerate("ABCD", 3, withRepetition: true)) {
        foreach (var x in n)
            Console.Write("{0} ", x);
        Console.WriteLine();
    }

以下は、上記コードを実行した結果です。長すぎるので、途中省略しています。


A A A
A A B
A A C
A A D
A B A
A B B
A B C
A B D
A C A
A C B
A C C
A C D
A D A
A D B
A D C
A D D
B A A
B A B
B A C
B A D
... 省略
C D B
C D C
C D D
D A A
D A B
D A C
D A D
D B A
D B B
D B C
D B D
D C A
D C B
D C C
D C D
D D A
D D B
D D C
D D D

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。