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

Question

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

and
adn
dan
dna
nad
nda

但是我希望它 return 该字符串中其余甚至 one/two 个字母的所有可能组合，如下所示：

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 到 and 的所有前缀，因此您应该改用：

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 您可以使用它，它不允许重复项，或者您可以检查是否添加之前是重复的。我会把优化留给你。

Answer 2

Powerset 不会 return 你想要什么。这是因为集合 {a, b, c} 等同于 {b, a, c} 以及您想要的其他集合。

您可以修改算法以从每个集合创建所有可能的排列。这将为您提供一些重复项，因此您可以将它们存储在集合中。

Answer 3

思考这个问题的一种方法是考虑给定集合的所有二进制组合。

例如，如果问题的集合是{a, b, c}，那么所有的二元组合（2^3 = 8）是：

000 = {}
001 = {c}
010 = {b}
011 = {b,c}
100 = {a}
101 = {a, c}
110 = {a, b}
111 = {a, b, c}

构建这些集合后，您可以使用递归来获取每个集合的组合。

Answer 4

public class Stringpermutations {
    public static void main(String[] args) {
        permutations(0,"123");
    }

    public static void permutations(int start, String s) {
        char[] chr=s.toCharArray();
        if(start==s.length()) {
            System.out.println(s);
        }
        for(int i=start;i<s.length();i++) {
            char c=chr[i];
            chr[i]=chr[start];
            chr[start]=c;
            permutations(start+1,new String(chr));
        } 
    }
}

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

Finding all possible combinations within a String using permutation

java

algorithm

android

permutation

powerset