JavaのArrayListを使って文字列の全順列を出力する方法

この記事では、長さnの文字列が与えられたときに、その文字列のすべての順列（並べ替え）を出力する方法を解説します。ポイントは、順列の結果をArrayListを使って管理・出力する点です。

問題の概要

具体例を見てみましょう。

• 入力： 文字列 = "XYZ"
• 出力： XYZ, XZY, YXZ, YZX, ZXY, ZYX

このように、入力された文字列の文字をすべて組み合わせた順列を、重複なく出力することが求められます。

解決アプローチ

この問題は再帰関数を使って解くのが効果的です。基本的な考え方は以下の通りです。

1. 文字列の先頭の1文字を取り出す。
2. 残りの部分文字列に対して再帰的に順列を生成する。
3. 返された順列リストの各要素に、先頭の文字をすべての挿入位置に挿入して新しい順列を作る。
4. 結果をArrayListとして返す。

再帰の終了条件は、文字列の長さが0になったときです。この場合は空文字列を含むArrayListを返し、そこから順次順列が組み立てられていきます。

実装例

以下は、ArrayListを使用したJavaでの実装例です。

import java.util.ArrayList;
public class Main {
    static void printArrayList(ArrayList<String> combo) {
        combo.remove("");
        for (int i = 0; i < combo.size(); i++)
            System.out.print(combo.get(i) + "\t");
    }
    public static ArrayList<String> generatePermutation(String str) {
        if (str.length() == 0) {
            ArrayList<String> empty = new ArrayList<>();
            empty.add("");
            return empty;
        }
        char ch = str.charAt(0);
        String subStr = str.substring(1);
        ArrayList<String> lastCombination = generatePermutation(subStr);
        ArrayList<String> newCombination = new ArrayList<>();
        for (String val : lastCombination) {
            for (int i = 0; i <= val.length(); i++) {
                newCombination.add(val.substring(0, i) + ch + val.substring(i));
            }
        }
        return newCombination;
    }
    public static void main(String[] args) {
        String str = "NOPQ";
        System.out.println("Permutations of string are :");
        printArrayList(generatePermutation(str));
    }
}

コードの解説

• generatePermutationメソッド： 再帰的に順列を生成する中核となるメソッドです。先頭文字を取り出し、残りの文字列で生成した順列の各位置にその文字を挿入していきます。
• printArrayListメソッド： 生成された順列のリストから空文字列を削除し、タブ区切りで画面に出力します。

実行結果

Permutations of string are :
NOPQ ONPQ OPNQ OPQN NPOQ PNOQ
PONQ POQN NPQO PNQO PQNO
PQON NOQP ONQP OQNP OQPN
NQOP QNOP QONP QOPN NQPO
QNPO QPNO QPON

4文字の文字列"NOPQ"の場合、順列の総数は4! = 24通りとなり、上記のようにすべての並べ替えパターンが出力されます。

計算量について

n文字の文字列の順列はn!通り存在するため、このアルゴリズムの時間計算量はO(n × n!)となります。文字列が長くなると順列の数は爆発的に増えるため、実用的にはnが10程度までが目安です。