引数arg
のすべての可能な分割を生成したいとします。 引数arg
は、arg.length - 1
ポイントに分割できます。 ここでは、ブール値の配列(divisors[N]
)を使用して、文字arg[N]
とarg[N + 1]
の間で分割するかどうかを覚えています。 divisors
のすべての可能なバージョンが再帰的なフローの間に生成されます。最後に達したら、文字列の分割を行い、結果を保存します。
public static void cover(final String arg) {
final List<Set<String>> result = new ArrayList<>();
final boolean[] divisors = new boolean[arg.length() - 1];
processDivisors(divisors, 0, arg, result);
System.out.println(result);
// now the result contains the divisions, we can do something with it
doSomethingWithResult(result);
}
private static void processDivisors(final boolean[] divisors,
final int position,
final String arg,
/* out */ final List<Set<String>> result) {
if (position == arg.length() - 1) {
final Set<String> computedDivision = computeDivision(arg, divisors);
result.add(computedDivision);
return;
}
divisors[position] = true;
processDivisors(divisors, position + 1, arg, result);
divisors[position] = false;
processDivisors(divisors, position + 1, arg, result);
}
private static Set<String> computeDivision(final String arg, final boolean[] divisors) {
final Set<String> computedDivision = new TreeSet<>();
int start = 0;
for (int i = 0; i < divisors.length; ++i) {
if (divisors[i]) {
computedDivision.add(arg.substring(start, i + 1));
start = i + 1;
}
}
computedDivision.add(arg.substring(start, arg.length()));
return computedDivision;
}
private static void doSomethingWithResult(final List<Set<String>> result) {
for (final Set<String> coverage : result) {
final String message = String.join("+", coverage);
System.out.println(message);
}
}
このコードは完全ではないと強く信じています。何とか最適化できます。 Btw。除算を行うときに余分な操作を行う必要がある場合は、computeDivison
メソッドを変更することができます。しかし、その部分を印刷に使うことは絶対にありません。最初に出力を生成してから別のコードセグメントで処理する方が賢明でしょう。
[指定された文字列のすべての順列を生成する](https://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string) – Mark