[C#] 順列を求める next_permutation() 代わりを実装する方法

C# で順列を求めたい

next_permutation – cpprefjp C++日本語リファレンス

C++ には next_permutation という順列を生成する関数が用意されています。これに似た関数を C# でもほしいので実装してみます。

next_permutation()

まずは next_permutation() がどんな関数か見てみます。

例えば [1, 2, 3] というようなソート済配列を引数に渡すと、以下のように辞書順で順列を生成します。

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

すべての並び順で n! 個(この場合3!=6個)の配列を生成してくれます。

こんな感じで使います。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
  vector<int> array = {1, 2, 3};
  do {
    for(int i = 0; i < 3; i++) {
      cout << array[i];
      if(i != 2) cout << " ";
    }
    cout << endl;
  } while(next_permutation(array.begin(), array.end()));
  return 0;
}

next_permutation() は次の順列が存在する場合はtrueを返し、そうでなければfalseを返します。trueを返したとき、引数の配列が次の順列に書き変わってます。

next_permutation() は C# には標準ライブラリで用意されていないので自分で実装していきます。

すべての順列を生成する関数の作り方

次のような関数を作成します。

• 引数で配列(T[])を渡して、辞書順ですべての順列(List<T[]>)を生成して返す
• 引数はソート済を渡す前提
• 辞書順で順列を生成するので T は比較可能な型(IComparable)

基本的にソート済のデータを渡してそれ以降の順列を生成します。なので [3, 2, 1] というデータを渡すと次の順列がないので1件だけ返します。

next_permutation() だと呼び出し時に do {} while(next_permutation()) みたいに書くのが面倒なので一括で順列を生成して返すようにします。

アルゴリズムと考え方

1. 隣り合う要素が昇順(a[i] < a[i+1])になっている一番大きい i を見つける
2. i が見つからないとき、全体が降順になっているので処理終了
3. 末尾から順番に見て、a[i] より大きい要素のインデックス j を見つける
4. a[i] と a[j] を入れ替え、i+1以降の要素を反転する

1 から順番に具体例を見ていきます。

基本的に完全に降順にソートされていれば、次の辞書順がありません。したがって部分的に昇順になっている個所で最も後ろの場所を降順に書き換えます。

1 2 3 ならi=1です。

1 2 3
  i 

2 3 1 ならi=0です。

2 3 1
i 

書き換える箇所はi番目です。

i番目の要素と置き換える要素を探します。i+1番目以降は降順になっているはずです。昇順になっている一番後ろの箇所がi番目だからです。

i番目の要素と交換するのは末尾から見て最初に見つかる a[i] より大きい要素です。

1 2 3
  i j

2 3 1
i j

i と j が決まったら交換します。交換後i+1番目以降を反転します。

1 2 3
  i j

上の例だと反転する箇所はありません。

2 1 3
i j

反転しないと正しい結果が得られません。降順の箇所にデータを挿入しているため、反転後は反転した箇所は昇順になります。

解説はこんな感じで。ということで実装してみます。

C# で実装

static List<T[]> AllPermutation<T>(params T[] array) where T : IComparable
{
    var a = new List<T>(array).ToArray();
    var res = new List<T[]>();
    res.Add(new List<T>(a).ToArray());
    var n = a.Length;
    var next = true;
    while (next)
    {
        next = false;

        // 1
        int i;
        for (i = n - 2; i >= 0; i--)
        {
            if (a[i].CompareTo(a[i + 1]) < 0) break;
        }
        // 2
        if (i < 0) break;

        // 3
        var j = n;
        do
        {
            j--;
        } while (a[i].CompareTo(a[j]) > 0);

        if (a[i].CompareTo(a[j]) < 0)
        {
            // 4
            var tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            Array.Reverse(a, i + 1, n - i - 1);
            res.Add(new List<T>(a).ToArray());
            next = true;
        }
    }
    return res;
}

実装上の注意として、すべての順列をまとめて返したいので配列をコピーしなければいけません。

res.add(new List<T>(a).ToArray());

ということで、リストに入れてコピーしてから配列に変換しています。

配列の部分的な反転は Array.Reverse(a, l, r) で 配列aのr番目からl番目の範囲を反転できます。

こんな感じです。

動作確認

順列の数は n! になります。

var p = AllPermutation(Enumerable.Range(1, 10).ToArray());
Console.WriteLine(p.Count); // 10!=3628800

順列が辞書順ですべて生成されます。

foreach (var item in AllPermutation(1, 2, 3, 4))
{
    Console.WriteLine(string.Join(" ", item));
}
// 1 2 3 4
// 1 2 4 3
// 1 3 2 4
// 1 3 4 2
// 1 4 2 3
// 1 4 3 2
// 2 1 3 4
// 2 1 4 3
// 2 3 1 4
// 2 3 4 1
// 2 4 1 3
// 2 4 3 1
// 3 1 2 4
// 3 1 4 2
// 3 2 1 4
// 3 2 4 1
// 3 4 1 2
// 3 4 2 1
// 4 1 2 3
// 4 1 3 2
// 4 2 1 3
// 4 2 3 1
// 4 3 1 2
// 4 3 2 1

いい感じです。

ABC 145 C – Average Length を解く

ということで作った AllPermutation() を使って、競技プログラミングの問題を解いてみます。

ABC 145 C – Average Length

座標平面上に N 個の町があります。町 i は、座標 ( x i , y i ) に位置しています。町 i と町 j の間の距離は √( ( x i − x j ) ^2 + ( y i − y j ) ^2) です。
これらの町を全て 1 回ずつ訪れるとき、町を訪れる経路は全部で N ! 通りあります。 1 番目に訪れる町から出発し、 2 番目に訪れる町、 3 番目に訪れる町、 … 、を経由し、 N 番目に訪れる町に到着するまでの移動距離 (町から町への移動は直線移動とします) を、その経路の長さとします。これらの N ! 通りの経路の長さの平均値を計算してください。

制約とかは問題ページで見てください。

これは順列ですべての順列を求められればあとは数式通りの計算をして平均をとるだけで答えが出ます。この問題を解くために順列生成関数を作ったわけです。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        // 入力
        var N = int.Parse(Console.ReadLine());
        var xy = new XY[N];
        for (int i = 0; i < N; i++)
        {
            var a = Console.ReadLine().Split(' ');
            xy[i] = new XY(int.Parse(a[0]), int.Parse(a[1]));
        }

        // インデックスを順列で全通りを求める
        var range = Enumerable.Range(0, N).ToArray();
        double sum = 0;
        var f = 0;
        foreach (var p in AllPermutation(range))
        {
            f++;
            // いろいろ計算
            double res = 0;
            for (int i = 0; i < p.Length - 1; i++)
            {
                res += Math.Sqrt(
                    Math.Pow(xy[p[i]].X - xy[p[i + 1]].X, 2) +
                    Math.Pow(xy[p[i]].Y - xy[p[i + 1]].Y, 2)
                );
            }
            sum += res;
        }

        // 最後に平均をとる
        var ans = sum / f;
        Console.WriteLine(ans);
    }

    static List<T[]> AllPermutation<T>(params T[] array) where T : IComparable
    {
        var a = new List<T>(array).ToArray();
        var res = new List<T[]>();
        res.Add(new List<T>(a).ToArray());
        var n = a.Length;
        var next = true;
        while (next)
        {
            next = false;
            int i;
            for (i = n - 2; i >= 0; i--)
            {
                if (a[i].CompareTo(a[i + 1]) < 0) break;
            }
            if (i < 0) break;

            var j = n;
            do
            {
                j--;
            } while (a[i].CompareTo(a[j]) > 0);

            if (a[i].CompareTo(a[j]) < 0)
            {
                var tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
                Array.Reverse(a, i + 1, n - i - 1);
                res.Add(new List<T>(a).ToArray());
                next = true;
            }
        }
        return res;
    }

    struct XY
    {
        public int X { get; set; }
        public int Y { get; set; }
        public XY(int x, int y)
        {
            this.X = x;
            this.Y = y;
        }
    }
}

AC したのでたぶんOKでしょう。

以上。