Javaで文字列の重複しない順列をすべて出力する方法

文字列の個別の順列（重複を除いた順列）をすべて出力するJavaプログラムは、以下の通りです。

サンプルコード

import java.util.ArrayList;
public class Demo{
   static boolean is_present(String my_str, ArrayList<String> rem){
      for (String str : rem){
         if (str.equals(my_str))
         return true;
      }
      return false;
   }
   static ArrayList<String> distinct_pattern(String str){
      if (str.length() == 0){
         ArrayList<String> base_Val = new ArrayList<>();
         base_Val.add("");
         return base_Val;
      }
      char ch = str.charAt(0);
      String rem_str = str.substring(1);
      ArrayList<String> prev_str = distinct_pattern(rem_str);
      ArrayList<String> rem = new ArrayList<>();
      for (String my_str : prev_str){
         for (int i = 0; i <= my_str.length(); i++){
            String f = my_str.substring(0, i) + ch + my_str.substring(i);
            if (!is_present(f, rem))
            rem.add(f);
         }
      }
      return rem;
   }
   public static void main(String[] args){
      String my_str = "mnqm";
      System.out.println("The distinct permutations of the string are ");
      System.out.println(distinct_pattern(my_str));
   }
}

実行結果

The distinct permutations of the string are
[mnqm, nmqm, nqmm, mqnm, qmnm, qnmm, mqmn, qmmn, mnmq, nmmq, mmnq, mmqn]

プログラムの解説

Demoという名前のクラスには、boolean型の関数「is_present」が定義されています。この関数は、指定された文字列がリスト内に既に存在するかどうかを確認し、存在すればtrue、存在しなければfalseを返します。

もう一つの関数「distinct_pattern」は、ArrayListを用いて順列を生成します。まず、文字列の長さが0になった場合に空文字列を要素とするリストを返す、再帰処理の基底ケースを設けています。

次に、文字列の先頭1文字を変数chとして取り出し、残りの部分をrem_strに格納します。その後、rem_strに対して「distinct_pattern」を再帰的に呼び出し、得られた各順列について、先頭文字を挿入できるすべての位置（0から文字列の長さまで）に順番に挿入していきます。

新しい順列を生成するたびに「is_present」による重複チェックを行うことで、同じ順列が複数回追加されるのを防ぎます。この仕組みにより、入力文字列に同じ文字が含まれていても、重複のない順列のみが出力されます。

main関数では文字列「mnqm」を定義し、それに対して「distinct_pattern」を呼び出して結果をコンソールに表示しています。入力文字列「mnqm」には「m」が2つ含まれているため、全順列4!＝24通りのうち、重複を除いた12通りの順列が出力されます。

補足：パフォーマンスを改善するには

本記事の実装では、重複チェックに線形探索（is_present）を使用しているため、文字列が長くなるほど計算時間が増大します。より効率的に処理したい場合は、HashSetを利用して既に生成済みの順列を管理すると、存在確認を高速（平均O(1)）に行えるため、パフォーマンスを大幅に向上させることができます。