赞
踩
如何用C语言实现整数的全排列?下面我来简单叙述
我目前掌握的是递归思想,相对好理解一些,只是效率不敢恭维。以后掌握其他方法还会来更新的。
先看效果
首先,我们先来思考,如何对四个数字,比如2345进行全排列?
可以这样思考,先固定2,即保持2是第一个位置不变,对345进行全排列。那如何对345进行全排列?先固定3,对45进行全排列。如何对45进行全排列?先固定4,那么只剩5了
显然,光这样是不够的,这只是递归思想的一个轮廓。为什么说这样是不够的呢,因为如果仅仅固定2对345进行全排列,显然不能称为2345 的全排列。同理,仅仅固定3对45进行全排列,也不能成为345的全排列。因此,对于每一个单位(2345是一个单位,345是一个单位,45是一单位),我们需要依次交换单位中每个元素与该单位第一个元素的位置,
然后每一个单位就会生成更多的子单位,
这些子单位进行上述相同的处理。
每次到末尾,就打印数组,开始进行递归中的“归”。值得一提的是,每次交换完并且执行递归函数后,都要再交换回去,方便下一次交换,比如,2345,交换3与2,变为3245,进行一组递归后,需交换回来重新变成2345从而方便4与2的交换。
```c int n = 0;//全局变量,作为计数器,计算进行了几次打印 Swap(int* a, int* b){ int tem = *a; *a = *b; *b = tem; } void perm(int arr[], int k, int m){//k的含义为从第arr[k]起,对后面的元素进行全排列。m为数组大小减一,即最后一个元素的下标,是递归结束的标志 if (k>m){ for (int i = 0; i <= m; i++){ printf("%d", arr[i]); } printf("\n"); n++; } else{ for (int i = k; i <= m; i++){ Swap(&arr[k], &arr[i]); perm(arr, k + 1,m); Swap(&arr[k], &arr[i]); } } } void main(){ int arr[] = { 2, 3, 4, 5 }; int sz = sizeof(arr) / sizeof(arr[0]); perm(arr, 0, sz-1); printf("总数为:%d!=%d\n", sz, n); }
``
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。