Chinaunix首页 | 论坛 | 博客
  • 博客访问: 536912
  • 博文数量: 45
  • 博客积分: 931
  • 博客等级: 准尉
  • 技术积分: 590
  • 用 户 组: 普通用户
  • 注册时间: 2005-04-17 13:27
文章分类

全部博文(45)

文章存档

2013年(6)

2012年(15)

2011年(23)

2005年(1)

分类: C/C++

2012-09-07 22:58:37

计算全排列有两种基本的方法, 递归和字典序。

1. 递归输出全排列

递归比较简单,下面直接贴代码:

点击(此处)折叠或打开

  1. void recurPermutation(int *arr, int n, int i)
  2. {
  3.     if(i==n-1) {
  4.         printArray(arr, n);
  5.     }
  6.     for(int j=i; j<n; j++) {
  7.         swap(arr, i, j);
  8.         recurPermutation(arr, n, i+1);
  9.         swap(arr, i, j);
  10.     }
  11. }
输入arr是一个长度是n的数组,数组元素各不相同。
 
2. 按字典序输出全排列
顾名思义是就是将1-n的一个排列看成一个数,然后按照字典的顺序从小到达的输出,
如1--5 的全排列,前面几个为:
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
....

如上面,我们如何由排列1 2 4 5 3得到1 2 5 3 4的呢?先从后往前扫描,找到排列的末尾的最大的递增子串,如最后的5 3;然后将这个子串反转, 得到了串1 2 4 3 5, 然后再刚才的末尾的子串中找出第大于4的最小的数, 即5, 然后将4和5交换。 这样就得到了 1 2 5 3 4了。

代码如下:

点击(此处)折叠或打开

  1. void permutation(int *arr, int n)
  2. {
  3.     int i, j, k;
  4.     int count = 1;
  5.     printArray(arr, n);
  6.     while(true) {
  7.         i=n-1;
  8.         while(i>0 && arr[i-1] > arr[i]) i--;
  9.         if (i==0) break;
  10.         
  11.         for(j=i, k=n-1; j<k; j++, k--) swap(arr, j, k);
  12.         for(j=i; j<n; j++) {
  13.             if(arr[j] > arr[i-1]) break;
  14.         }
  15.         
  16.         swap(arr, i-1, j);
  17.         count ++;
  18.         printArray(arr, n);
  19.     }
  20.     printf("Total permutations: %d\n", count);
  21. }
其中,输入参数是1...N的有序数组;如果无序的话,可以用快排进行排序。

由于排列的问题能够很好的考查对递归的掌握程度,并且实现也非常的简单,因此经常会出现在面试之中。

下面就是某著名互联网公司的一道关于排列的面试题:
题目:输入一个字符串S和一个整数N,其中S中的各个字符均不相等,并且N小于等于S的长度,请输出由S中字符组成的长度为N的所有的排列。
如:字符串是"abc", N=2, 则输出:ab, ac, bc, ba, ca, cb

阅读(12606) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~