非递归数组全排列

发布时间:2016-12-8 14:12:20 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"非递归数组全排列",主要涉及到非递归数组全排列方面的内容,对于非递归数组全排列感兴趣的同学可以参考一下。

首先我想说, 太TM操蛋了, 排序那部分代码一直让我纠结了好久!!!非递归思想, 参考的网上的, 代码是自己写的, 勉强算原创吧!!! 这个算法如果想要获取到单调递增的全排列, 需要先将所给数组排序, 然后再调用part()函数即可!!! 思想如下:  n个数的排列可以从1.2....n开始,至n.n-1....2.1结束。  也就是按数值大小递增的顺序找出每一个排列。  以6个数的排列为例,其初始排列为123456,最后一个排列是654321,  如果当前排列是124653,找它的下一个排列的方法是,从这个序列中  从右至左找第一个左邻小于右邻的数,如果找不到,则所有排列求解  完成,如果找得到则说明排列未完成。本例中将找到46,计4所在的  位置为i,找到后不能直接将46位置互换,而又要从右到左到第一个  比4大的数,本例找到的数是5,其位置计为j,将i与j所在元素交换  125643,然后将i+1至最后一个元素从小到大排序得到125346,这  就是124653的下一个排列,如此下去,直至654321为止。算法结束。   #include <stdio.h> #include <string.h> int isDesc(char a[] , int length){ int i=0; for(; i < length; i++){ if(a[i]>=a[i+1]){ continue; }else{ break; } } if(i==length) return 1; else return 0; } void swap(char a[], int src , int dest){ char temp = a[src]; a[src]=a[dest]; a[dest]=temp; } void sort(char a[], int n){ int i,j,temp; for(j=0;j<n-1;j++) for(i=0;i<n-1-j;i++) if(a[i] > a[i+1]) //数组元素大小按升序排列 { temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } } int findFirst(char a[] , int length , int *bigpos){ /*find the first left < right return the left one get the bigger one whose position bigger than the left length is the num of charactor */ int pos = -1; for(int i = length-1 ; i >= 0 ; i--){ if(pos == -1) { if(i==0){ break; }else{ if(a[i-1]<a[i]){ pos = i-1; }else{ continue; } } }else{ break; } } int j = length; for(; j > pos ; j--){ if(a[j] > a[pos]) { *bigpos = j; break; } } return pos; } void part(char a[] , int length){ //length is the num of charact if(isDesc(a, length)){ return ; }else{ int start = 0; int end = length-1; /*123 = length = 3 end = 2*/ while(!isDesc(a,length)){ int temp = -1; int pos = -1; printf("%s\n",a); pos = findFirst(a,length,&temp); swap(a,pos,temp); sort(&a[pos+1],end-pos); } printf("%s\n",a); } } int main(){ char b[5]= "abcc"; part(b,4); return 0; }    

上一篇:HDU-#1000 A + B Problem
下一篇:x7xu8dadasdawadad

相关文章

相关评论