C#:攪乱順列を求める

攪乱順列とは

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メソッドで２つの要素を比較しているのがミソですね。

ジェネリックメソッドにしていますので、== 使えないので、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で公開したものを加筆・修正したものです。