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

C#:攪乱順列を求める

More than 1 year has passed since last update.

攪乱順列とは

1,2,3,4..Nの要素からなる順列において、i番目の要素が iでない順列を攪乱(かくらん)順列といいます。完全順列とも言うようです。

複数人でプレゼントを交換する場合のパターンだと言えば具体的イメージが湧くと思います。

C#のコード

    public static class Derangement {
        // 攪乱順列(完全順列ともいう)を列挙する
        public static IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items) {
            var original = items.ToArray();
            foreach (var element in Permutation.Enumerate(items, items.Count(), false)) {
                bool isComplete = element.Zip(original, (a, b) => a.Equals(b))
                                         .All(x => x == false);
                if (isComplete)
                    yield return element;
            }
        }
    }

    public static class Permutation {
        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 };
                var unused = withRepetition ? items : items.Except(leftside);
                foreach (var rightside in Enumerate(unused, k - 1, withRepetition)) {
                    yield return leftside.Concat(rightside).ToArray();
                }
            }
        }
    }

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

簡単な解説

攪乱順列を求めるのに、「n個の異なった要素の中から k個を選ぶ順列」で示したPermutationクラスをそのまま利用しています。

攪乱順列を求めるDerangementクラスでは、まず、このPermutationクラスを使い、普通の(重複のない)順列を求め、次に、i 番目の要素が、オリジナルの i番目の要素と一致する場合を取り除くという当たり前すぎる方法で、攪乱順列を求めています。

このi番目の要素と一致する場合を取り除くところで、LINQの ZipメソッドとAllメソッドを使っています。Zipメソッドで2つの要素を比較しているのがミソですね。

ジェネリックメソッドにしていますので、== 使えないので、Equalsメソッドで2つの値を比較しています。

Derangementの利用サンプル

以下、Derangementクラスの利用サンプルです。

  static void Main(string[] args) {
      int n = 4;
      var nums = Enumerable.Range(1, n).ToArray();
      var derangements = Derangement.Enumerate(nums);

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

結果は以下の通りです。

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

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