这种递归排列代码是如何工作的?

Question

public class Permutation 
{ 
public static void main(String[] args) 
{ 
String str = "ABC"; 
int n = str.length(); 
Permutation permutation = new Permutation(); 
permutation.permute(str, 0, n-1); 
} 
private void permute(String str, int l, int r) 
{ 
if (l == r) 
System.out.println(str); 
else
{ 
for (int i = l; i <= r; i++) 
{ 
str = swap(str,l,i);     
permute(str, l+1, r); ``
str = swap(str,l,i); 
} 
} 
} 
public String swap(String a, int i, int j) 
{ 
char temp; 
char[] charArray = a.toCharArray(); 
temp = charArray[i] ; 
charArray[i] = charArray[j]; 
charArray[j] = temp; 
return String.valueOf(charArray); 
} 
} 

我不明白这段代码将如何生成字符串的排列

str = swap(str,l,i);     
permute(str, l+1, r);
str = swap(str,l,i); 

Answer 1

permute方法通过将索引中的字符从lr(含(排列，将可从str获取的所有字符串打印到标准输出。假设l <= r.

这回答了你的问题吗？好吧，至少这是答案的一个非常核心的部分。

我相信 markspace 有一个很好的观点：研究在调试器中运行的递归方法。观察调用堆栈的增长和收缩，并检查堆栈帧及其中的变量。

与此同时，我的贡献是我对递归方法的思考方式。对我来说，编写递归方法是编写调用尚未实现的方法的代码的特例。相信它可以并且将在以后实施。我希望你熟悉这种编写代码的方式。

我上面的第一段指定了permute方法的行为。让我们研究一下实现如何实现此行为。

首先，如果l和r相等，也就是说，它们指向相同的字符，则不需要交换，因为只有一个排列，即该字符已经位于正确位置的排列。因此，打印str并退出。

如果l严格小于r，该方法依次将范围内的每个字符放入位置l。这是获得所有排列所必需的。对于放在l的每个字符，它会以所有可能的方式将所有剩余字符排列在剩余位置，即通过rl + 1。它是如何做到这一点的？好吧，我们已经指定了一个可以为我们执行此操作的方法，因此只需调用该方法即可。如果它让你感到困惑，我们调用的方法就是我们已经使用的方法，那么暂时不要去想这个事实。假设我们正在调用一个我们信任的不同方法来完成这项工作。最后，在调用该方法之后，我们将字符交换回其原始位置，以便为下一次通过循环做好准备。