返回顶部

收藏

C++求数组的全排列之字典序法

更多

字典序法说明: 字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。 它的整体思想是让排列成为可递推的数列,也就是说从前一状态的排列,可以推出一种新的状态,直到最终状态。比如说,最初状态是12345,最终状态是54321。 1.最初状态为12345,从最后面向前面比较,因为5>4,所以从4后面的序列中找出一个比4大,但是比在4后面的序列中最小的数,因为只有5,所有将4和5调换位置,结果为12354. 2.将原来4后面的序列进行倒置,因为现在只有1个4,倒置后还是12354. 3.已12354为基础,继续上面的步骤进行操作,下一序列的生成步骤如下: 12354(5>3)->12354(4,5序列中最小但是比3大的是4)->12453(调换4和3)->12435(将5,3倒置)```cpp

include <stdio.h>

include <ctype.h>

include <malloc.h>

static void swapNum(int i, int j, int intArray, int num); static int getSmallestButGreatThanIndex(int intArray, int num, int j, int i); static void invertIntArray(int i, int intArray, int num); static void prtIntArray(int intArray, int num);

int main(int argc,char argv[]){ int num = 0; int intArray = NULL; int i = 0; int j = 0;

//检查参数,必须是2个
if(argc != 2){
    printf("there must be one parameter!\n");
    goto FINALLY;
}

//检查参数,参数必须是数字
char* ptr = argv[1];
while(*ptr != '\0'){
    if(isdigit(*(ptr++)) == 0){
        printf("please input a numble!\n");
        goto FINALLY;
    }
}

//将参数转换成int型
num = atoi(argv[1]);
intArray = (int*)malloc(sizeof(int) * num);
//初始化数组:1,2,3,4,5,6......
for(i=0; i<num; i++){
    intArray[i] = i+1;
}

//打印下原始数组
printIntArray(intArray, num);
//从数组最后面往前比较
for(i=num-1,j=num-2; i>=1 &amp;&amp; j>=0; i--,j--){
    //如果右边数的比左边数的大
    if(intArray[i] > intArray[j]){
        //将左边的数与右边数组中最小但是比左边的数大的数交换
        swapNum(i, j, intArray, num);
        //将左边数右边的数组序列倒置
        invertIntArray(i, intArray, num);
        //将整个数组打印
        printIntArray(intArray, num);
        //继续从数组的最后面往前面比较
        i = num;
        j = num - 1;
    }
}

FINALLY: if(intArray != NULL){ free(intArray); intArray = NULL; } return 0; }

static void swapNum(int i, int j, int* intArray, int num){ int swapi = getSmallestButGreatThanIndex(intArray, num, j, i); int temp = intArray[j]; intArray[j] = intArray[swapi]; intArray[swapi] = temp; }

static int getSmallestButGreatThanIndex(int* intArray, int num, int j, int i){ int m = 0; int swapi = 0; int smallest = num + 1; for(m = i; m<num; m++){ if(intArray[m] > intArray[j] &amp;&amp; intArray[m] < smallest){ swapi = m; smallest = intArray[m]; } } return swapi; }

static void invertIntArray(int i, int* intArray, int num){ int m; int n; int temp; for(m=i, n=num-1; (m-n)<0; m++,n--){ temp = intArray[m]; intArray[m] = intArray[n]; intArray[n] = temp; } }

static void printIntArray(int* intArray, int num){ int i; for(i=0; i<num; i++){ printf("%d ",intArray[i]); } printf("\n"); }

```

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning