不知道这个字符串排列代码是如何工作的

Question

我无法理解这个字符串排列代码是如何工作的。我理解它是如何将字符从str移动到前缀的，但当我跟踪它是如何工作的时，我完全不知道它是如何进入下一个排列的。

例如单词"cubs">

它的输出是字符串前缀+"+字符串字符串

幼崽

瑞银

铜-硼

幼崽

幼崽我知道它是如何到达这里的

cu bs<----------我不明白它是怎么从这里开始的？

public static void main(String[] args) {
permutation("cubs");        
}
public static void permutation(String str) {
permutation("", str);
}
public static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) {
System.out.println(prefix);         
}
else {
for (int i = 0; i < n; i++) {
System.out.println(prefix + " " + str);
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));               
}
}
}

Answer 1

不确定是否正确解释了您的问题。我想你想知道为什么你有这个复制品，对吧？我进一步假设，你不仅仅想要一个有效的解决方案，因为你可能想自己解决这个问题，对吧？

在for循环中，您打印一些内容，在某些情况下，当递归调用permutation时，这些内容将再次打印。

您在循环中打印的事实使这种情况很可能发生。如果只在循环外打印(if (some condition) print(this); else print that(，可以更容易地避免重复。

实际上，您可能不想在else部分打印任何内容。

Answer 2

好的，让我看看我能不能为你解释一下。考虑递归的最好方法是将其视为一个层次结构——每个嵌套调用都是层次结构中的下一级。

因此，当你用"、"幼崽"来称呼perm时，它会依次调用以下内容：

c,ubs
u,cbs
b,cus
s,cub

如果你考虑第一个呼叫"c"，"ubs"，它会呼叫：

cu,bs
cb,us
cs,ub

其中第一个"cu"、"bs"将使用args调用：

cub,s
cus,b

这些"幼崽"中的第一个"s"将使用args调用：

cubs,

现在第二个参数字符串的长度为0，因此没有更深层次的递归。

把c，ubs的整个层次结构放在一起，看起来像

,cubs
c,ubs
cu,bs
cub,s
cubs,
cus,b
cusb,
cb,us
cbu,s
cbus,
cbs,u
cbsu,
cs,ub
cus,b
cusb,
cub,s
cubs,
u,cbs
...

希望你能看到这将如何通过每一个组合轮流工作。

你特别问它是如何在"cu-bs"开始的。原因是在每次迭代中都要打印prefix + " " + str，所以它会在每次递归调用之前打印相同的文本3次。如果您想跟踪递归，那么在调用开始时打印一次可能更有意义。函数主体中的以下内容可能会给出更有意义的输出：

System.out.println(prefix + " " + str);
for (int i = 0; i < str.length(); i++) {
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, str.length())); 
}