Javaで文字列のすべての順列（並び替え）を出力する方法

本記事では、Javaを使用して文字列のすべての順列（パーミュテーション）を生成し出力する方法を解説します。

順列とは

順列とは、文字列に含まれる文字をさまざまな順序で並べ替えた組み合わせのことです。例えば「hey」という3文字の文字列の場合、6通りの並べ方（3! = 6）が存在します。一般に、重複する文字がない文字列の長さがnであれば、n!通りの順列が生成されます。

サンプルプログラム

以下は、文字列のすべての順列を出力するJavaプログラムの例です。

public class Demo{
    static void print_permutations(String my_str,String my_ans){
        if (my_str.length() == 0){
            System.out.print(my_ans + " ");
            return;
        }
        boolean my_arr[] = new boolean[26];
        for (int i = 0; i < my_str.length(); i++){
            char ch = my_str.charAt(i);
            String remaining_str = my_str.substring(0, i) + my_str.substring(i + 1);
            if (my_arr[ch - 'a'] == false)
            print_permutations(remaining_str, my_ans + ch);
            my_arr[ch - 'a'] = true;
        }
    }
    public static void main(String[] args){
        String my_str = "hey";
        System.out.println("The permutation of the string are :");
        print_permutations(my_str, "");
    }
}

実行結果

The permutation of the string are :
hey hye ehy eyh yhe yeh

プログラムの仕組み

クラスDemoには、静的メソッド「print_permutations」が定義されています。このメソッドは、まず引数として渡された文字列が空かどうかをチェックし、空であればそれまでに構築された文字列「my_ans」を出力して処理を終了します。

次に、サイズ26のブール型配列「my_arr」を用意します。デフォルトではすべての要素がfalseになっています。この配列は、小文字のアルファベット（a〜z）がすでに使用済みかどうかを記録するためのもので、ある文字を使用したタイミングで対応するインデックスの値がtrueに更新されます。これにより、同じ文字から始まる重複した順列が何度も出力されるのを防ぐことができます。

その後、「for」ループを使って文字列の長さ分だけ繰り返し処理を行い、i番目の文字を一つずつ取り出します。i番目の文字を除いた残りの部分文字列は、「remaining_str」という変数に格納されます。対象の文字がまだ使用されていない場合、残りの文字列と現在の結果を連結した文字列を引数として、再帰的にメソッドを呼び出します。すでに使用済みの文字である場合は、再帰呼び出しは行われません。

mainメソッドでは、対象となる文字列「hey」を定義し、初期値として空文字列を渡しながらprint_permutationsメソッドを呼び出しています。この再帰的なアプローチにより、すべての順列が効率よく生成・表示されるのです。