全排列之非递归实现

基本思想是: 1.对初始队列进行排序，找到所有排列中最小的一个排列Pmin。 2.找到刚刚好比Pmin大比其它都小的排列P(min+1)。 3.循环执行第二步,直到找到一个最大的排列,算法结束。 如排列ABCDE，这是所有排列中最小的一个排列，刚好比ABCDE大的排列是：ABCED。 算法如下： 给定已知序列P = A1A2A3.....An 对P按字典排序，得到P的一个最小排列Pmin = A1A2A3....An ，满足Ai > A(i-1) (1 < i <= n) 从Pmin开始,找到刚好比Pmin大的一个排列P(min+1)，再找到刚好比P(min+1)大的一个排列，如此重复。 1.从后向前（即从An->A1）,找到第一对为升序的相邻元素，即Ai < A(i+1)。 若找不到这样的Ai，说明已经找到最后一个全排列，可以返回了。 2.从后向前,找到第一个比Ai大的数Aj，交换Ai和Aj。 3.将排列中A(i+1)A(i+2)....An这个序列的数逆序倒置，即An.....A(i+2)A(i+1)。因为由前面第1、2可以得知，A(i+1)>=A(i+2)>=.....>=An,这为一个升序序列，应将该序列逆序倒置，所得到的新排列才刚刚好比上个排列大。 4.重复步骤1-3,直到返回。 这个算法是C++ STL算法next_permutation的思想。 #include <stdio.h> #include <iterator> #include <iostream> using namespace std; bool next(int list[], int length) { for (int i = length - 1; i >= 1; i--) { if (list[i] > list[i-1]) return 1; } copy(list,list+length,ostream_iterator<int>(cout," ")); return 0; } //交换数组a中下标为i和j的两个元素的值 void swap(int *list, int i, int j) { int temp; temp = list[i]; list[i] = list[j]; list[j] = temp; } //将数组a中的下标i到下标j之间的所有元素逆序倒置 void reserve(int list[], int begin, int end) { int i,j; for(i = begin, j = end; i < j; i++,j--) swap(list, i ,j); } void prem(int list[], int length) { int i,j; if(length <= 1) return ; while(next(list, length)) {//求取全排列,打印结果 copy(list,list+length,ostream_iterator<int>(cout," ")); cout<<endl; for (i = length -2; i >= 0; i--){ if( list[i] < list[i+1]) break; } for( j = length - 1;j > i; --j ) if (list[i] < list[j]) break; swap(list, i, j); reserve(list, i+1, length-1); } } int main() { int list[3] = {1, 2, 3}; prem(list, sizeof(list)/sizeof(int)); //prem(list, 3); }

二．补充 去掉重复的全排列的递归实现 在上篇博客“全排列之递归实现”中没有考虑去掉全排列中重复的数字， 如 1 2 2 输出为：1 2 2 1 2 2 2 1 2 2 2 1 2 2 1 去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。下面给出完整代码：

#include <stdio.h> #include <iostream> #include <iterator> using namespace std; //在pszStr数组中，[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等 bool IsSwap(int list[], int begin, int end) { for ( int i = begin; i < end; i++ ) if (list[i] == list[end]) return false; return true; } void swap(int *p, int *q) { int temp; temp = *p; *p = *q; *q = temp; } void perm(int list[],int begin, int end) { if ( begin == end ) { copy(list,list+end+1,ostream_iterator<int>(cout," ")); cout<<endl; } for (int i = begin; i <= end; i++) { if(IsSwap(list, begin, i)) { swap( &list[begin], &list[i]); perm(list, begin + 1, end); swap( &list[begin], &list[i]); 注意恢复原样 } } } int main() { int list[]={1,2,2}; perm(list, 0, 2); //0,4 分别是数组的下标 return 0; }