从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。如果如果输入为1、2、3,要求输出123、132、213、231、312和321。下面分有重复元素和无重复元素的两种情况说明:
一、无重复元素的递归算法实现
无重复元素的全排列问题,用递归算法比较简单。代码如下:
#include <stdio.h> #define NUM 3 int arr[NUM] = {1, 2, 3}; void do_range(int low, int high) { if(low == high) { for(int i=0; i<NUM; i++) printf("%6d", arr[i]); printf("\n"); } else { do_range(low+1, high); for(int i=low+1; i<=high; i++) { //递归前交换 int t = arr[low]; arr[low] = arr[i]; arr[i] = t; do_range(low+1, high); //递归后复位 t = arr[low]; arr[low] = arr[i]; arr[i] = t; } } } int main(int argc,char *argv[]) { do_range(0, NUM-1); return 0; }
输出如下:
1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2
二、有重复元素的递归算法实现
如果有重复元素,比如输入113,再按照上述算法,输出如下,显然不符合要求。
1 1 3 1 3 1 1 1 3 1 3 1 3 1 1 3 1 1
关键问题就是有重复元素,算法中就不需要进行交换,再递归求解了。上述代码修改如下:
#include <stdio.h> #define NUM 3 int arr[NUM] = {1, 1, 3}; void do_range(int low, int high) { if(low == high) { for(int i=0; i<NUM; i++) printf("%6d", arr[i]); printf("\n"); } else { do_range(low+1, high); for(int i=low+1; i<=high; i++) { //如果有重复元素,就不要交换再递归求解了。直接过滤就行。 if(arr[low] == arr[i]) continue; //递归前交换 int t = arr[low]; arr[low] = arr[i]; arr[i] = t; do_range(low+1, high); //递归后复位 t = arr[low]; arr[low] = arr[i]; arr[i] = t; } } } int main(int argc,char *argv[]) { do_range(0, NUM-1); return 0; }
输出如下:
1 1 3 1 3 1 3 1 1
上述输出结果符合要求,完毕~~~