C#でバックトラッキングを使って文字列のすべての順列を求める方法

バックトラッキング（backtracking）は、すべての候補を体系的に試しながら、行き詰まったら直前の状態に戻って別の選択肢を探索するアルゴリズム手法です。文字列の順列生成にも効果的に活用できます。

バックトラッキングによる順列生成の考え方

まず、先頭の位置に置く文字を選び、残りの文字を先頭の文字と入れ替えます。たとえば「ABC」という文字列の場合、1回目の反復で A を A・B・C のそれぞれと入れ替えることにより、「ABC」「BAC」「CBA」の3つの文字列が生成されます。

続いて、2番目の文字 B を固定するように、残りの文字についても同じ手順を繰り返します。その後、元の並びに戻すためにもう一度入れ替えを行います。これがバックトラック（巻き戻し）です。たとえば「ABC」から B を固定して「ABC」を得た後、ひとつ前の状態へ戻り、B と C を入れ替えることで「ACB」が得られます。この処理を再帰的に繰り返すことで、すべての順列を漏れなく列挙できます。

アルゴリズムの手順

1. 開始位置（start）と終了位置（end）が一致したら、その時点の文字列を出力する（1つの順列が完成）
2. 一致していなければ、start から end までの各文字 i について以下を繰り返す
   • start 番目の文字と i 番目の文字を入れ替える
   • start を1つ進めて自分自身を再帰呼び出しする
   • 入れ替えを元に戻して、次の候補に備える（バックトラック）

C#での実装例

using System;
namespace ConsoleApplication{
    public class BackTracking{
        public void StringPermutation(string word, int start, int end){
            if (start == end){
                Console.WriteLine(word);
            }
            else{
                for (int i = start; i <= end; i++){
                    Swap(ref word, start, i);
                    StringPermutation(word, start + 1, end);
                    Swap(ref word, start, i);
                }
            }
        }
        private void Swap(ref string word, int start, int end){
            char[] arr = word.ToCharArray();
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            word = new string(arr);
        }
    }
    class Program{
        static void Main(string[] args){
            BackTracking b = new BackTracking();
            b.StringPermutation("ABC", 0, 2);
        }
    }
}

このコードでは、StringPermutation メソッドが再帰的に呼び出され、各段階で文字を入れ替えては元に戻すことで全パターンを探索します。Swap メソッドは C# の string が不変（イミュータブル）であるため、一旦 char 配列に変換してから入れ替えを行い、新しい文字列として再構築している点に注目してください。

実行結果

ABC
ACB
BAC
BCA
CBA
CAB

計算量について

n 文字の文字列が持つ順列は n! 通り存在するため、このアルゴリズムの時間計算量は O(n × n!) となります。文字数が少し増えるだけでも組み合わせの総数は爆発的に増加するため、長い文字列に対して使用する場合は注意が必要です。