Question

递归的全排列产生算法

大概知道是怎么回事，就是先固定a,然后考虑(b,c)的所有排列......
但是对这段代码就不太理解了，比如为什么要由if(i==n)，后面的两个的SWAP都是怎么回事？可不可以详细说明一下？

Answer 1

我说说我对这段程序的大致理解过程。水平有限，难免纰漏。

咋一看我也理解不了，只是知道了函数第二个参数i表示首元素，第三个参数n表示尾元素。于是我开始按照数学归纳法的方式来理解（我一直觉得递归算法要按照数学归纳法的方式才好理解）。
我印象中数学归纳法的要点好像是包括如下2点：
1.初始的几种情况，即n=0，n=1的情况；
2.第k次与第k-1次间的关系，即已知第k-1次的结果，如何求出第k次的结果。

放到这个问题中：
1.通过考虑n=0，n=1等的几种情况，我大概知道了这个函数的最终结果是打印出一组全排列。不过有些实现细节还没完全明白。
2.已知k-1个元素的全排列，如何求出k个元素的全排列？结合perm函数中的递归调用是把第二个参数加1，我就想出这个问题的答案了：首先确定首元素的值，这样，需要全排列的元素就少了1个，递归也就成立了。

想到这里应该就差不多了，整个算法的思路是：
从元素0开始依次确定各个元素的值，当确定了最后一个元素的值时，就打印整个数组。

最后回答下你的问题：
1.if语句就是当确定了最后一个元素的值后的处理；
2.两个swap实现的就是确定首元素的算法。
另外这里要用两个swap是为了保证全排列后各元素顺序不会乱，否则会出现将相同的元素swap到首位置的情况。这个结论是我又用了一次数学归纳法的思考方式才得出的。