C中数字的排列
我正在尝试编写一个C函数来列出一组数字的所有排列,以五个为一组,包括重复数字:
15-11-49-43-5 2-30-34-6-11
所以编写一个函数来获取一个数字集的所有排列并将它们抛出是很容易的,但是映射到某个组大小,我有点卡住..
void visit(int *Value, int N, int k) { static level = -1; level = level+1; Value[k] = level; if (level == N) print(Value, N); else for (int i = 0; i < N; i++) if (Value[i] == 0) visit(Value, N, i); level = level-1; Value[k] = 0; }
有关更多信息,请访问http://www.bearcave.com/random_hacks/permute.html
你想得到一个特定的排列,例如
- 置换1 == 1,1,1,1,1
- 置换2 == 1,1,1,1,2
- 置换49 == 1,1,1,1,49
- 置换50 == 1,1,1,2,1
- 置换42000000 == 8,14,49,35,42
将您想要的数字(减1)转换为基数49,并使用“数字”(加1)作为结果。
42000000 - 1 = 41999999 41999999 =(7 * 49 ^ 4)+(13 * 49 ^ 3)+(48 * 49 ^ 2)+(34 * 49)+ 41 结果8 14 49 35 42
如果您知道如何查找所有排列而不是所有大小为5的组合,那么只需查找以下所有排列:
int A [49] = {0,0,…,0,1,1,1,1,1};
数组A的每个排列对应于包含数字(i + 1)的组合,当且仅当A [i] == 1时,对于[0,49]中的每个i。
由于允许重复,并且输出集小于输入集,因此它实际上并不是您所追求的排列。
你只是在寻找一个简单的计数:
for (a[0] = 1; a[0] <= 49; a[0]++) for (a[1] = 1; a[1] <= 49; a[1]++) for (a[2] = 1; a[2] <= 49; a[2]++) for (a[3] = 1; a[3] <= 49; a[3]++) for (a[4] = 1; a[4] <= 49; a[4]++) printf("%d-%d-%d-%d-%d\n", a[0], a[1], a[2], a[3], a[4]);
我将其分解为两个问题:a)找到大小为nb的数组的所有组合nCk)找到长度为k的数组的所有排列。 你说你已经知道如何进行排列了,所以让我们专注于组合:
void combinations(int *arr, int *comb, int n, int k, int kCurr) { if(kCurr >= k) { permutations(comb, k); return; } int i; for(i=0; i
这将被称为:
int myArray[49] = {1, 2, ..., 49}; int myCombs[5]; combinations(myArray, myCombs, 49, 5, 0);
这通过构建数组myCombs
计算所有组合49C5,当它满时它调用函数permutations
。 如果permutations
正确实施,那么您将打印出49C5的所有组合的所有排列。
编辑:Duh,你可以做combinations(arr, comb, n, k kCurr+1)
作为递归步骤,然后只需在基本情况下打印数组(或做任何事情)。