在dev c++中 用c语言写一个全排列（不能用递归）
在dev c++中 用c语言写一个全排列（不能用递归） 指针尽量避免使用 给出代码同时有注释 另外算法也写上（设计思路）
[解决办法]
基本思想是:
1.找到所有排列中最小的一个排列P.
2.找到刚刚好比P大比其它都小的排列Q,
3.循环执行第二步,直到找到一个最大的排列,算法结束.
下面用数学的方法描述:
给定已知序列 P = A1A2A3An ( Ai!=Aj , (1<=i<=n , 1<=j<=n, i != j ) )
找到P的一个最小排列Pmin = P1P2P3Pn 有 Pi > P(i-1) (1 < i <= n)
从Pmin开始,总是目前得到的最大的排列为输入,得到下一个排列.
方法为:
1.从低位到高位（从后向前），找出“不符合趋势”的数字。即找到一个Pi，使Pi < P(i+1)。
若找不到这样的pi，说明我们已经找到最后一个全排列，可以返回了。
2.在 P(i+1)P(i+2)Pn 中,找到一个Pj,便得 Pj"刚刚好大于"Pi.
("刚刚好大于"的意思是:在 P(i+1)P(i+2)Pn 中所有大于Pi的元素构成的集合中最小的元素.)
3.交换 Pi , Pj 的位置.注意:此处不改变i和j的值,改变的是Pi和Pj.
4.交换后， P1P2P3Pn 并不是准确的后一个排列。因为根据第1步的查找，我们有P(i+1) > P(i+2) > . > Pn
即使进行了Pi和Pj的交换,这仍然是这一部分最大的一个排列。将此排列逆序倒置(变成最小的排列)即为所求的下一个排列.
5.重复步骤1-4,直到步骤1中找不到“不符合趋势”的数字.
//交换数组a中下标为i和j的两个元素的值void swap(int* a,int i,int j){ a[i]^=a[j]; a[j]^=a[i]; a[i]^=a[j];} //将数组a中的下标i到下标j之间的所有元素逆序倒置void reverse(int a[],int i,int j){ for(;i<j;++i,--j) { swap(a,i,j); }} void print(int a[],int length){ for(int i=0;i<length;++i) cout<<a[i]<<" "; cout<<endl;} //求取全排列，打印结果void combination(int a[],int length){ if(length<2) return; bool end=false; while(true) { print(a,length); int i,j; //找到不符合趋势的元素的下标i for(i=length-2;i>=0;--i) { if(a[i]<a[i+1]) break; else if(i==0) return; } for(j=length-1;j>i;--j) { if(a[j]>a[i]) break; } swap(a,i,j); reverse(a,i+1,length-1); }}
[解决办法]
#include<stdio.h>#include<stdlib.h>#include<malloc.h>int func(const int *array, int size){ int *tab; int cnt, cur; int i; if (NULL == array || size <= 0) { return 0; } cnt = 0; cur = 0; if (NULL == (tab = (int *)malloc(size * sizeof(int)))) { return 0; } tab[0] = -1; while (cur >= 0) { do { tab[cur] += 1; for (i = 0; i < cur; ++i) { if (tab[cur] == tab[i]) { break; } } }while (tab[cur] < size && i != cur); if (tab[cur] < size) { if (size - 1 == cur) { for (i = 0; i < size; ++i) { printf("%d ", array[tab[i]]); } printf("\n"); ++cnt; } else { cur += 1; tab[cur] = -1; } } else { cur -= 1; } } free(tab); return cnt;}int main(){ int a[] = {1, 2, 3, 4, 5}; printf("共有%d中全排列情况\n", func(a, sizeof(a) / sizeof(a[0]))); system("pause"); return 0;}