从数组中取出n个元素的所有组合（递归实现）

2023-06-29 22:01| 来源: 网络整理| 查看: 265

今天在做POJ 1753时，需要枚举一个数组中所有组合。之前也遇到过类似的问题，如求从n个数组任意选取一个元素的所有组合都是想起来比较简单，但是设计成算法却颇费周折。如数组为{1, 2, 3, 4, 5, 6}，那么从它中取出3个元素的组合有哪些，取出4个元素的组合呢？比如取3个元素的组合，我们的思维是：取1、2，然后再分别取3，4，5，6；取1、3，然后再分别取4，5，6；......取2、3，然后再分别取4，5，5；......这样按顺序来，就可以保证完全没有重复。

这种顺序思维给我们的启示便是这个问题可以用递归来实现，但是仅从上述描述来看，却无法下手。我们可以稍作改变：1.先从数组中A取出一个元素，然后再从余下的元素B中取出一个元素，然后又在余下的元素C中取出一个元素2.按照数组索引从小到大依次取，避免重复

依照上面的递归原则，我们可以设计如下的算法，按照索引从小到大遍历：

1 //arr为原始数组 2 //start为遍历起始位置 3 //result保存结果，为一维数组 4 //count为result数组的索引值，起辅助作用 5 //NUM为要选取的元素个数 6 //arr_len为原始数组的长度，为定值 7 void combine_increase(int* arr, int start, int* result, int count, const int NUM, const int arr_len) 8 { 9 int i = 0; 10 for (i = start; i < arr_len + 1 - count; i++) 11 { 12 result[count - 1] = i; 13 if (count - 1 == 0) 14 { 15 int j; 16 for (j = NUM - 1; j >= 0; j--) 17 printf("%d\t",arr[result[j]]); 18 printf("\n"); 19 } 20 else 21 combine_increase(arr, i + 1, result, count - 1, NUM, arr_len); 22 } 23 }

当然，我们也可以按照索引从大到小进行遍历：

1 //arr为原始数组 2 //start为遍历起始位置 3 //result保存结果，为一维数组 4 //count为result数组的索引值，起辅助作用 5 //NUM为要选取的元素个数 6 void combine_decrease(int* arr, int start, int* result, int count, const int NUM) 7 { 8 int i; 9 for (i = start; i >=count; i--) 10 { 11 result[count - 1] = i - 1; 12 if (count > 1) 13 { 14 combine_decrease(arr, i - 1, result, count - 1, NUM); 15 } 16 else 17 { 18 int j; 19 for (j = NUM - 1; j >=0; j--) 20 printf("%d\t",arr[result[j]]); 21 printf("\n"); 22 } 23 } 24 }

测试代码：

1 #include 2 3 int main() 4 { 5 int arr[] = {1, 2, 3, 4, 5, 6}; 6 int num = 4; 7 int result[num]; 8 9 combine_increase(arr, 0, result, num, num, sizeof(arr)/sizeof(int)); 10 printf("分界线\n"); 11 combine_decrease(arr, sizeof(arr)/sizeof(int), result, num, num); 12 return 0; 13 }

输出结果为：

1 1 2 3 4 2 1 2 3 5 3 1 2 3 6 4 1 2 4 5 5 1 2 4 6 6 1 2 5 6 7 1 3 4 5 8 1 3 4 6 9 1 3 5 6 10 1 4 5 6 11 2 3 4 5 12 2 3 4 6 13 2 3 5 6 14 2 4 5 6 15 3 4 5 6 16 分界线 17 6 5 4 3 18 6 5 4 2 19 6 5 4 1 20 6 5 3 2 21 6 5 3 1 22 6 5 2 1 23 6 4 3 2 24 6 4 3 1 25 6 4 2 1 26 6 3 2 1 27 5 4 3 2 28 5 4 3 1 29 5 4 2 1 30 5 3 2 1 31 4 3 2 1

【本文地址】

公司简介

联系我们