java - 使用排列查找字符串中所有可能的组合

Question

我目前有两种方法使用递归来为我提供给定 String 的所有可能组合，我是在这个 answer 的帮助下完成的.因此，如果我输入 String 并返回这些组合:

and
adn
dan
dna
nad
nda

但是我希望它返回该字符串中其余甚至一个/两个字母的所有可能组合，如下所示:

a
n
d
an
ad 
na
nd
etc...

Something like this answer but in java

该答案还提到并链接了 Powersets它显示了 a、b、c 的所有可能子集:

如您所见，它不会像

这样从后往前进行组合

c,b,a
c,a,b
c,a
....

这是我想要实现的当前代码:

public void permutation(String str) {

  permutation("", str);
}

private void permutation(String prefix, String str) {

    int n = str.length();
    if (n == 0) myList.add(prefix);
    else {
        for (int i = 0; i < n; i++)

            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));

    }
}

Answer 1

    if (n == 0) myList.add(prefix);

您提供的这条语句仅在您排列了 str 中可用的所有字符时才添加它。

如果你删除 if (n == 0) 它会添加从 a 到 an 到 的所有前缀和，所以你会改用:

private void permutation(String prefix, String str) {
    int n = str.length();
    myList.add(prefix);
    if(n > 0) {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));

    }

由于递归，您显然会得到一堆重复项，并且可能会得到一个空字符串，但是您可以使用一个不允许重复项的 Collection，或者您可以检查如果它在添加之前是重复的。我会把优化留给你。