混合多个变量的算法

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()函数