再帰で順列をつくる

再帰で順列を作るサンプルです。

• ABCD の順列をつくりたい
• A を除いた BCD で順列を作り、先頭に A を付けると A が先頭の順列ができあがる
  • B を除いた ACD で順列を作り、先頭に B を付けると B が先頭の順列ができあがる
  • C を除いた ABD で……(以下同様)
• 1 文字の順列は、自身そのものである

ポイントは再帰呼び出しと、ベースケース(再帰呼び出しをせずに呼び出し元に戻る部分)の構造を見抜くことです。

• 自分自身から 1 文字取り除いた(1 文字少ない)文字列の順列を再帰呼び出しで作る
• 自分自身の文字列の長さが 1 のときは、自身をそのまま返す(ベースケース)

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

class Program {
    static List<string> Perms(string s) {
        if (s.Length == 1) return new List<string>() { s };
        // ↑は以下でもよい
        // if (s.Length == 0) return new List<string>() { "" };

        var ret = new List<string>();
        for (int i = 0; i < s.Length; i++) {
            // 1. s[i] を除いたグループで順列を作る(再帰)
            foreach (string t in Perms(s.Remove(i, 1))) {
                // 2. 先頭に s[i] をつけると
                //    s[i] が先頭の順列が出来る(長さ s.Length の順列)
                ret.Add(s[i] + t);
            }
        }
        return ret;
    }

    static void Main() {
        foreach (var s in Perms("abcd")) {
            Console.WriteLine(s);
        }
    }
}

実行結果です。

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba