如果现在有六个数字1 2 3 4 5 6,请列举出其所有的排列可能。
从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。显然,这是一个全排列问题。
全排列问题是递归的代表题型。
递归思想
如果我想对从1到6的六个数字做全排列,我可以:
- 首先,我固定第一个数字是1,然后对后面的数字做全排列。
- 然后,我固定第一个数字是2,然后对后面的数字做全排列。
- 以此类推,第一个数字再固定3、4......一直到6。
当我固定第一个数字是1的时候,还剩下2、3、4、5、6,我只需要对剩下的这5个数字做全排列,就可以解决“当第一个数字是1的时候,所有的全排列可能性”的问题了,显然,第一个数字依次从1到6遍历一遍,可以求解这六个数的全排列所有可能性。
那么再思考,第一个数字被固定了,后面的数字是不是又是一个新的全排列问题呢?
第一个数字如果固定了1,后面还剩下2、3、4、5、6,把后面的2、3、4、5、6单独拿出来看,我再次固定后面那部分的第一个数字(也就是固定整体的第二个数字)是2,对3、4、5、6进行全排列,我再固定这四个数字这一部分的第一个数字(也就是整体的第三部分)是3,对4、5、6进行全排列......
递归的思想显而易见,如果想求解全排列问题,步骤很简单:
- 固定好第一个数字
- 对后面的数字进行全排列
- 重新固定第一个数字,并重复第二个步骤,直到所有的数字都在第一个位置上走过一遍了。
代码实现
递归思想有了以后,实现起来并不难,关键点有:
把一个数放在第一个位置,就是将其与第一个位置上的数交换
假如现在我有六个数1、2、3、4、5、6,现在做全排列,第一步是当1开头时,很显然,1本来就是第一个数字,看第二步,当2是开头时......诶?怎么写呢?
我们可以理解成,把2与第一个位置上的数字换一换,变成2,1,3,4,5,6,现在我们就不用看第一个位置了,从第二个位置开始看进行新的全排列即可。
关键点在于,每次换完并且求解出所有“子全排列问题”以后,一定要换回来!
代码实现
#include<cstdio>
//交换两个位置上的数字
void swap(int num[666], int i, int j) {
int t = num[j];
num[j] = num[i];
num[i] = t;
}
//输出一个数组
void disp(int num[666], int length) {
for (int i = 0; i < length; ++i) {
printf("%d ", num[i]);
}
printf("\n");
}
//全排列的实现
void qpl(int num[666], int length, int startLoc) {
for (int i = startLoc; i < length; ++i) {
swap(num, startLoc, i);
//如果发现当前要解决的子问题只有一个数字,
//就不用再往下开子问题了
if (startLoc < length - 1)
qpl(num, length, startLoc + 1);
else //如果要是只有一个数字,输出当前的数组,当前数组就是当前的全排列可能性
disp(num, length);
swap(num, startLoc, i);
}
}
int main() {
int num[666] = {1, 2, 3, 4, 5, 6};
qpl(num, 6, 0);
return 0;
}