0

示例：我有从 1 到 10 的数字。所有可能的组合，在每个组合中，每个变量都包含一次，没有任何重复，是......嗯...... 3628800 (10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800）。

就我而言，计算机必须检查所有组合，而不是随机选择组合。之后，系统会将所需的组合存储在一个数组中。但是我想不出一种算法，也找不到在互联网上的算法（可能是因为我没有找到正确的方法）。

我可以使用什么算法来混合多个变量，其中所有组合都没有重复变量？

4

3 回答 3

5

您可以为此尝试递归方法。

这个想法是“猜测”哪个数字将是第一个，设置它 - 然后递归数组的剩余部分。如果你对所有剩余的元素做这些“猜测”，你就会得到所有可能的排列。

这是打印给定数组的所有排列的通用 C 代码（不处理数组中的重复值）：

void permute(int *array,int i,int length) { 
  if (length == i){
     printArray(array,length);
     return;
  }
  int j = i;
  for (j = i; j < length; j++) { 
     swap(array+i,array+j);
     permute(array,i+1,length);
     swap(array+i,array+j);
  }
  return;
}

在这种方法中：用您的数字预先填充一个数组：1,2,...,n- 并在其上调用排列算法。

您可以通过一个简单的测试用例来查看它，包括ideoneprint()中的andswap()函数

于 2012-07-18T12:36:11.137 回答
1

您要查找的内容称为permutations。

维基百科列出了几种不同的方式：

获得所有排列的慢方法

一种天真的慢方法包括创建一个给定整数 i 的函数，返回第 i 个排列，然后调用函数 N！次。

看看这个问题的答案在这里。

有序方式

Lexicographic 方法描述为：

以下算法在给定排列之后按字典顺序生成下一个排列。它就地改变了给定的排列。

  1. 找到满足 a[k] < a[k + 1] 的最大索引 k。如果不存在这样的索引，则排列是最后一个排列。

  2. 找到最大的索引 l 使得 a[k] < a[l]。由于 k + 1 是这样一个索引，所以 l 是很好定义的并且满足 k < l。

  3. 将 a[k] 与 a[l] 交换。

  4. 反转从 a[k + 1] 到最后一个元素 a[n] 的序列。

您应该首先对序列进行排序以按顺序排列所有排列。

最小交换

可能更快，但我没有在我的快速浏览中看到任何代码示例。

考虑Steinhaus-Johnson-Trotter 算法的描述。

于 2012-07-19T00:58:14.607 回答
0

似乎您正在尝试打乱您的整数集：Fisher-Yates shuffle

于 2012-07-18T12:34:26.393 回答