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

  • 0
    いいね
  • 0
    コメント

    全ての要素を使った順列を求める」で書いたコードをすこし手直しするだけで、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の数が1ずつ減ってゆくわけですが、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();
            }
        }
    }
    

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

    重複なしの実行例

      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で公開したものを加筆・修正したものです。