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

C#:n個の要素からk個を選ぶ組合せを列挙する

More than 1 year has passed since last update.

組み合わせとは

組み合わせの具体的な例(重複を許さない組み合わせと重複を許す組み合わせ)を以下に示します。

重複を許さない場合、{1,2,3,4,5}の5つの要素の中から 3個を選ぶ組合せは、以下の通りです。

(1,2,3)
(1,2,4)
(1,2,5)
(1,3,4)
(1,3,5)
(1,4,5)
(2,3,4)
(2,3,5)
(2,4,5)
(3,4,5)

重複を許す場合の組合わせは以下のようになります。

(1,1,1)
(1,1,2)
(1,1,3)
(1,1,4)
(1,1,5)
(1,2,1)
(1,2,2)
... 途中省略 ...
(5,5,1)
(5,5,2)
(5,5,3)
(5,5,4)
(5,5,5)

C#のコードを書いてみる。

ここでは、n個の異なる要素の中から k個を選ぶ組合せを列挙するプログラムを書いてみます。

書いたのが以下のCombinationクラスです。

重複を許さない場合と許す場合の両方に対応しています。

  public static class Combination {
      public static 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 };

              // item よりも前のものを除く (順列と組み合わせの違い)
              // 重複を許さないので、unusedから item そのものも取り除く
              var unused = withRepetition ? items : items.SkipWhile(e => !e.Equals(item)).Skip(1).ToList();

              foreach (var rightside in Enumerate(unused, k - 1, withRepetition)) {
                  yield return leftside.Concat(rightside).ToArray();
              }
          }
      }
  }

ソースコードは、GitHubで公開しています。

n個の異なった要素の中から k個を選ぶ順列」で掲載したコードと見比べてほしいのですが、考え方はほぼ同じです。

順列の場合と違い、(オリジナルの順番でみて)自分よりも前の要素は候補から外すようにしています。

ちょっとわかりにくい表現ですが、例をあげればわかると思います。例えば、この処理によって、{ 1, 2, 3 } は列挙されますが、 { 2, 1, 3 } や { 3, 2, 1 }などは列挙されなくなります。

Combinationの利用サンプル

上記のCombinationクラスを利用するサンプルコードです。

  static void Main(string[] args) {
      int n = 5;
      int k = 3;
      var nums = Enumerable.Range(1, n).ToArray();
      var combinations = Combination.Enumerate(nums, k, withRepetition:false);

      int i = 1;
      foreach (var elem in combinations) {
          string s = "(" + string.Join(",", elem.Select(x => x.ToString()).ToArray()) + ")";
          Console.WriteLine("{0} : {1}", i++, s);
      }
  }

以下のような結果が得られます。

1 : (1,2,3)
2 : (1,2,4)
3 : (1,2,5)
4 : (1,3,4)
5 : (1,3,5)
6 : (1,4,5)
7 : (2,3,4)
8 : (2,3,5)
9 : (2,4,5)
10 : (3,4,5)

この記事は、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
ユーザーは見つかりませんでした