Java で特定の文字列のすべての順列を検索する

順列は、配置の順序が重要な場合に、セット内の可能な配置の数を決定するための数学的手法です。

再帰を使用した文字列の順列

関数 permutationFinder(String str) は再帰的で、渡された文字列のすべての順列を出力します。Set 変数は、重複が自動的に削除されるように Java 文字列の順列を格納するために使用されます。文字列内で一度に 1 文字ずつ単語を切り刻み、残りの文字を個別に処理します。

insertChar 関数は最初の文字を挿入して、渡した文字列の順列の完全なリストを取得します。

文字列 ABC から始めて、一度に 1 文字ずつ繰り返します。最初の文字 A を分離し、残りの文字は BC です。ここで、rem を繰り返し処理し、残りの文字の順列を見つけます。このプロセスについては、以下でさらに説明します。

permutationFinder() 関数は、チョップするものがなくなるまで起動されます。そのため、rem = ""を取得します。この時点で、""を perms に追加して返します。これはさらに Set 変数 words に格納されます。また、現時点での initial の文字は C であることを忘れないでください。

Set 単語の各文字列をループします。""の空の文字列として strNew があります。この場合は 2 番目の for ループになります。strNew.length() に等しい i=0 があります。したがって、その時点の引数を使用して insertChar("",C,0) メソッドを呼び出します。この呼び出しは、perm に追加された C を返します。

ループを抜けて、未完成のビジネスがあるかどうかを確認します。したがって、この時点で、initial 値は B になり、words には C という 1つの要素があります。ここで、C を使用して異なる位置に B を追加することにより、ループが繰り返されます。したがって、BC と CB は、Set ワード内の 2つの要素として取得されます。

この時点で、ループから抜け出し、initial 値を A として取得します。さらにこのプロセスを繰り返し、最初の文字 A を以前の順列の可能な位置に挿入します。まず、BC の場合、ABC``BAC と BCA を取得します。同様に、2 番目の順列 CB についても同じことを行います。最初の文字を可能な位置に挿入し、ACB、CAB、および CBA を取得します。

import java.util.HashSet;
import java.util.Set;

public class PermutationFinder {
  public static Set<String> permutationFinder(String str) {
    Set<String> perm = new HashSet<String>();
    if (str == null) {
      return null;
    } else if (str.length() == 0) {
      perm.add("");
      return perm;
    }
    char initial = str.charAt(0);
    String rem = str.substring(1);
    Set<String> words = permutationFinder(rem);
    for (String strNew : words) {
      for (int i = 0; i <= strNew.length(); i++) {
        perm.add(insertChar(strNew, initial, i));
      }
    }
    return perm;
  }

  public static String insertChar(String str, char c, int j) {
    String begin = str.substring(0, j);
    String end = str.substring(j);
    return begin + c + end;
  }
  public static void main(String args[]) {
    String s1 = "ABC";
    System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
  }
}

これらはすべて、文字列 ABC の可能な順列です。

出力：

Permutations for ABC are: 
[ACB, BCA, ABC, CBA, BAC, CAB]