Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What is going on with this article?

More than 3 years have passed since last update.

@gushwell

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

全ての要素を使った順列を求める」で書いたコードをすこし手直しするだけで、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で公開したものを加筆・修正したものです。

4
Help us understand the problem. What is going on with this article?
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
4
Help us understand the problem. What is going on with this article?