我目前有两种方法,它们使用递归来给出给定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));
}
}
最佳答案
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
,或者在添加之前检查它是否是重复项。我把优化工作交给你来做。