混合多个变量的算法

Question

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

在我的例子中，计算机必须检查所有组合，而不是随机选择组合。之后，系统会将需要的组合存储在一个数组中。但是我想不出一种算法，而且我在互联网上也找不到(可能是因为我搜索的方式不正确)。

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

Answer 1

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

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

这是打印给定数组的所有排列的一般情况 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 - 并对其调用排列算法。

您可以通过一个简单的测试用例看到它，包括 ideone 中的 print() 和 swap() 函数