1

我正在尝试编写一个 C 函数来列出一组数字的所有排列，以五个为一组，包括重复数字：

15-11-49-43-5
2-30-34-6-11

所以很容易编写一个函数来抓取一个数字集的所有排列并将它们扔掉，但是映射到某个组大小，我有点卡住了..

4

5 回答 5

1

你想得到一个特定的排列，比如

  • 排列 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
于 2010-09-22T09:07:07.427 回答
1 
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

于 2010-09-21T23:30:13.340 回答
0

如果您知道如何找到所有排列但不是所有大小为 5 的组合，那么只需找到以下所有排列：

int A[49] = { 0, 0, ..., 0, 1, 1, 1, 1, 1 };

数组 A 的每个排列对应于包含数字 (i+1) 的组合，当且仅当 A[i] == 1，对于 [0, 49) 中的每个 i。

于 2010-09-22T01:58:12.077 回答
0

由于允许重复，并且输出集小于输入集，因此它实际上根本不是您想要的排列。

您只是在寻找一个简单的计数：

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]);
于 2010-09-22T02:13:48.187 回答
0

我会将其分为两个问题：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<n; ++i)
    {
        comb[kCurr] = arr[i];
        combinations(arr+i, comb, n-i, k, kCurr+1);
    }
}

这将被称为：

int myArray[49] = {1, 2, ..., 49};
int myCombs[5];
combinations(myArray, myCombs, 49, 5, 0);

这通过构建数组来计算所有组合 49C5 myCombs，当它满了时它调用一个函数permutations。如果permutations实施得当，那么您将打印出 49C5 的所有组合的所有排列。

编辑：Duh，你可以做combinations(arr, comb, n, k kCurr+1)递归步骤，然后在基本情况下打印数组（或做任何事情）。

于 2010-09-22T00:33:50.410 回答