void Permutation(int n) { unsigned int *a = new unsigned int[n];//用来存储n个自然数 for (int i=0; i<n; i++) //存储全排列的元素值,并计算全排列的数量 { a[i] = i + 1; } Recursion(a, n, 1); delete []a; } void Recursion(unsigned int a[], int n, int k) { if (k > n) Print(a, n); else { int temp; for (int i=0; i<k; i++)//循环左移 { temp = a[0]; for (int j=1; j<k; j++) a[j-1] = a[j]; a[k-1] = temp; Recursion(a, n, k+1); } } }
#include <stdio.h> void swap(int &a, int &b) { int temp; temp = a; a = b; b = temp; } bool nextPermutation(int *p, int n) { int last=n-1; int i,j,k; //从后向前查找,看有没有后面的数大于前面的数的情况,若有则停在后一个数的位置。 i=last; while(i>0&&p[i]<p[i-1]) i--; //若没有后面的数大于前面的数的情况,说明已经到了最后一个排列,返回false。 if(i==0) return false; //从后查到i,查找大于p[i - 1]的最小的数,记入k k=i; for(j=last; j>=i; j--) if(p[j]>p[i-1]&&p[j]<p[k]) k =j; //交换p[k]和p[i - 1] swap(p[k],p[i-1]); //倒置p[last]到p[i] return true; } //显示一个排列 void showPermutation(int *p, int n) { for(int i=0; i<n; i++) printf("%d ",p[i]); printf("\n"); } int main(int argc, char *argv[]) { int n; int *p; scanf("%d",&n); p = new int[n]; for (int i = 0; i < n; i++) p[i] = i + 1; showPermutation(p, n); while(nextPermutation(p, n)) { showPermutation(p, n); } //delete[] p; return 0; }
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
循环移位法是一种很容易理解的非有序全排列算法,它的原理是:如果已经生成了K-1个元素的排列,则在每个排列后添加元素k使之成为k个元素的排列,然后将每个排列循环左移,每移动一次就产生一个新的排列。
例如2个元素的排列是 1 2 和 2 1,在1 2后加上成为新排列 1 2 3,将它循环左移可再生成新排列 2 3 1、3 1 2, 同样 2 1 可生成新排列 2 1 3、 1 3 2和3 2 1.
代码也很简单,使用了递归穷举思想,下面是一个循环左移的算法:
非递归算法
主要的任务在nextPermuation()中完成。这其中的思想是,提供一个已经有的全排列P,求出P的“下一个”全排列。这里“下一个”的意思是说,在n个数的n!个全排列在数字上从小到大的一个序列中,p的下一个数字上比它大的一个排列。
那么由此,提供一个初始的n个数的全排列P1 = p1p2…pn,有pi > pi – 1(1 < i < n – 1),反复运行nextPermuation()找出比P的“下一个”全排列,直到Pn! = p1’p2’…pn’,pi < pi – 1
(1 < i < n – 1)为止。所找到的所有的排列就是n的全排列。
下面要考虑的问题,是如何从一个已知的排列P = p1p2…pn,找到它的下一个排列
Q = q1q2…qn。我们要让排列从小到大生成,简单说,要让排列的趋势从p1p2…pn,pi > pi – 1(1 < i < n – 1),到p1’p2’…pn’,pi < pi – 1(1 < i < n – 1)。因此:
1. 从低位到高位(从后向前),找出“不符合趋势”的数字。即找到一个pi,使pi – 1 < pi。若找不到这样的pi,说明我们已经找到最后一个全排列,可以返回了。
2. 把pi - 1替换成从pn到pi几个数字中“刚刚好大于pi-1”的数字。这里的目的是找出准确的P的下一个排列Q。所谓“刚刚好大于”,我们就查找从pi到pn中大于pi-1的最小的数字。然后将找到的数字与pi-1交换。
3. 还没有结束。交换后,pi-1pi…pn并不是准确的后一个排列。因为根据第一步的查找,我们有pi > pi+1 > … > pn,否则查找在i~n就会停下来了。这样的一个排列显然不是最小的。实际上,原来的pi…pn,已经是这一部分最大的一个排列了。但我们现在换了最高位pi-1,因此要让后面的数字变的最小。方法很简单,根据上面的推理,我们只须将pi~pn的数列倒置即可(最大的排列倒置就变成了最小的排列)。这样,我们计算出了准确的下一个排列。
ps:这个主要的思想就是,当每次我们交换完之后,交换之后的后面的部分是一个符合趋势的排列,为了得到所有的排列,我们将其反转,那就相当于对其部分再进行一次方向最大排列的问题。倒过来再倒过去从而达到了遍历。