c - 打印给定元素排列的程序

Question

我最近参加了 ACM 认证的编程竞赛。这是我当时做不到的问题:

“给定一个包含 n 个元素的整数数组，编写一个程序来打印所有排列。”

请告诉我这道题该怎么做。有没有什么算法可以做这类题？

Answer 1

假设没有重复:只需用所有可能的后续元素更改每个元素，然后递归调用该函数。

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;
}

您可以在 ideone 处看到带有辅助函数 swap() 和 printArray() 的代码在基本测试用例中的执行情况。

奖励:这与fisher-yates shuffle的想法类似。 ，但在这里 - 不是将 i 处的元素与随机选择的后续元素交换 - 你可以将其与所有元素交换 - 一次每个元素。