Java の文字列を全置換する方法

2年 ago
光, 明
1 minute

文字列の全並びを生成するには、再帰的手法を使うことができる。

具体的な手順は以下のとおりです。

  1. 文字列と２つのインデックスパラメータ（現在の並びの開始位置と終了位置）を受け取る再帰関数を作成します。
  2. スタート位置と終了位置が等しい場合、一通りの並びが完了したことを表し、現在の文字列を出力する。
  3. それ以外の場合は、現在の文字列を２つの部分に分割する。１文字目と残りの文字列部分。
  4. 最初の1文字目を残りの文字それぞれと交換し、新たな文字列を得ます。
  5. 関数を再帰呼び出しし、新しい文字列とインデックスを +1 した引数を渡します。
  6. 再帰関数がリターンした後に、最初の文字を元に戻し、次の交換を行います。

以下にJavaコードで実装した例を示します。

public class Permutation {
    public static void main(String[] args) {
        String str = "abc";
        permute(str.toCharArray(), 0, str.length() - 1);
    }

    public static void permute(char[] arr, int start, int end) {
        if (start == end) {
            System.out.println(new String(arr));
        } else {
            for (int i = start; i <= end; i++) {
                swap(arr, start, i);
                permute(arr, start + 1, end);
                swap(arr, start, i);
            }
        }
    }

    public static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

このコードは、文字列 “abc” の順列をすべて出力します。

abc

bannerAds