【C#】順列全探索を実装してみる

はじめに

今回は順列全探索を実装してみる記事になります！

順列全探索とは

順列全探索とは通りの順列を生成して探索をすることです。

例えば{1, 2, 3}の順列の組み合わせは以下の通りです。

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

この組み合わせの数は「通り」ということになります。

これはどのようにコードで実現していくかというと、順列は以下の図のような構造になっていることを応用します。

これは{1, 2, 3, 4}の順列を木構造で表したものですが、こういった木構造は再帰処理をすることで列挙できることが一般的に知られています。

実際の方針はこちら。

1. コレクション(今回は{1, 2, 3, 4})からそれぞれの要素を選択する
2. 未確定の要素が一つだけならそれを返す
3. 選択した要素を確定し、未確定の要素たちに対して２を呼ぶ
4. 選択した要素を連結する

コード

public static IEnumerable<T[]> GetPermutation<T>(IEnumerable<T> collection)
{
    // 未確定要素が一個のみ
    if (collection.Count() == 1)
    {
        yield return new T[] { collection.First() };
    }

    foreach (var item in collection)
    {
        var selected = new T[] { item };
        var unused = collection.Except(selected);

        // 確定した要素以外の組み合わせを再帰で取り出し連結
        foreach (var rightside in GetPermutation(unused))
        {
            yield return selected.Concat(rightside).ToArray();
        }
    }
}

使い方

static void Main(string[] args)
{
    // {1, 2, 3}の順列をすべて列挙する
    foreach (var item in GetPermutation(Enumerable.Range(1, 3)))
    {
        Console.WriteLine(string.Join(" ", item));
    }
}

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1