Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした