赞
踩
这是普通的实现:**
#include<iostream> #include<time.h> #include<algorithm> using namespace std; //交换 void swap(int arr[],int i , int j) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void Perm(int list[] , int k ,int m) { //list 数组存放排列的数,k表示层 代表第几个数,m表示数组的长度 if(k==m) { //K==m 表示到达最后一个数,不能再交换,最终的排列的数需要输出; //for(int i=0 ;i<=m ;i++) // cout<<list[i]; //cout<<endl; return ; } else{ for(int i=k;i<=m;i++) { swap(list, i, k); Perm(list,k+1,m); swap(list, i, k); } } } int main(void) { clock_t t1 = clock(); int a[10]; for(int i = 0; i < 10; i ++) { a[i] = i; } int n = sizeof a/sizeof a[0]; Perm(a, 0, n); cout <<"time is "<< (clock() - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << endl; return 0; }
O(n*n!)
#include<iostream> #include<time.h> #include<algorithm> using namespace std; //交换 void swap(int arr[],int i , int j) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } //打印 void printArr(int a[],int n) { for (int i=0; i<n; i++) cout << a[i] << " "; printf("\n"); } void heapPermutation(int a[], int size, int n) { if (size == 1) { //printArr(a, n); return; } for (int i=0; i<size; i++) { heapPermutation(a,size-1,n); if (size%2==1) //奇数 swap(a,0,size-1); else //偶数 swap(a,i,size-1); } } int main() { clock_t t1 = clock(); int a[11]; for(int i = 0; i < 11; i ++) { a[i] = i; } int n = sizeof a/sizeof a[0]; heapPermutation(a, n, n); cout <<"time is "<< (clock() - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << endl; return 0; }
O(n!)
(我猜的)这个算法的描述:
见维基百科:
https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
截了些图想看就看吧,我是不想看了,会用就好(哈哈)
非递归伪代码:
非递归实现:
void heapPermutation2(int arr[],int n) { int c[n]; for(int i = 0; i < n; i++) { c[i] = 0; } //printArr(arr,n); int i = 0; while(i < n) { if(c[i] < i) { if(i%2 == 0) { swap(arr,0,i); } else { swap(arr,c[i], i); } // printArr(arr,n); c[i]++; i = 0; } else { c[i] = 0; i++; } } }
小优化:
void heapPermutation(int a[], int size, int n) { if (size == 1) { //printArr(a, n); return; } for (int i=0; i<size; i++) { heapPermutation(a,size-1,n); if(i < size-1) { if (size%2==1) swap(a,0,size-1); else swap(a,i,size-1); } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。