java - 替换Java中的String以获取所有变体

Question

我正在尝试打印某个字符串的所有变体。例如，我们有这样的输入:AB0C0。第三个和第五个位置的 0 应被视为变量。变量字符是 1、2 和 3，将放置在 0 的位置。这意味着此输入将有所有可能的变化:

1. AB1C1
2. AB2C1
3. AB3C1
4. AB1C2
5. AB1C3
6. AB2C2
7. AB2C3
8. AB3C2
9. AB3C3

这只是一个例子。 5 个字符的长字符串可容纳 1 到 5 个变量。我面临的问题是，无论输入中有多少变量，无论它们位于哪个位置，它都应该生成所有变体。

Scanner scanner = new Scanner (System.in);
System.out.println("Enter the key consisting of 5 characters:");
String input = scanner.next();
String strOutput1 = input.replaceFirst("0","1");
String strOutput1A = input.replace("0","1");
String strOutput2 = input.replaceFirst("0","2");
String strOutput3 = input.replaceFirst("0","3");
String strOutput4 = input.replaceFirst("0","4");
String strOutput5 = input.replaceFirst("0","5");
System.out.println(strOutput1.toUpperCase());
System.out.println(strOutput1A.toUpperCase());
System.out.println(strOutput2.toUpperCase());
System.out.println(strOutput3.toUpperCase());
System.out.println(strOutput4.toUpperCase());
System.out.println(strOutput5.toUpperCase());

Answer 1

这个怎么样:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

public static void main(String[] args) throws Exception {
    Scanner scanner = new Scanner(System.in);
    System.out.println("Enter the key consisting of 5 characters:");
    String input = scanner.next();

    //find positions of '0' in input
    List<Integer> varPositions = findVarPositions(input);

    //create permutations
    List<String> permutations = new ArrayList<>();
    permutations.add(input);//AB0C0
    for (int position : varPositions) {
        permutations = permutateAtPosition(permutations, position);
    }

    //print permutations
    for (String permutation : permutations) {
        System.out.println(permutation.toUpperCase());
    }
}

private static List<Integer> findVarPositions(String input) {
    List<Integer> varPositions = new ArrayList<>();
    int lastVarPosition = -1;
    while ((lastVarPosition = input.indexOf('0', lastVarPosition + 1)) != -1) {
        varPositions.add(lastVarPosition);
    }
    return varPositions;
}

private static List<String> permutateAtPosition(List<String> partialyPermutated, int position) {
    List<String> result = new ArrayList<>();
    char[] replacements = {'1', '2', '3', '4', '5'};
    for (String item : partialyPermutated) {
        for (int i = 0; i < replacements.length; i++) {
            String output = replaceCharAt(item, position, replacements[i]);
            result.add(output);
        }
    }
    return result;
}

private static String replaceCharAt(String input, int position, char replacement) {
    //converting to char array, because there's no method like
    //String.replaceAtPosition(position, char)
    char[] charArray = input.toCharArray();
    charArray[position] = replacement;
    return new String(charArray);
}

}

它并不固定于许多变量。

这个想法是提取“0”的位置，然后调用方法permutateAtPosition，该方法采用部分排列的列表并将其再排列一层。

对于“a0b0c0”和值 1-2，则为 ['a0b0c0']，然后是 ['a1b0c0','a2b0c0']，然后是 ['a1b1c0','a1b2c0','a2b1c0','a2b2c0']，最后['a1b1c1','a1b1c2','a1b2c1','a1b2c2','a2b1c1','a2b1c2 ','a2b2c1''a2b2c2']。

此解决方案将所有内容保留在内存中，因此在一般情况下(无限输入字符串)，使用深度优先会更明智。