c++ - 提高给定字符串所有排列的时间复杂度

Question

问题通常是给定一个字符串，打印它的所有排列。例如，字符串 ABC 的排列是 ABC、ACB、BAC、BCA、CAB、CBA。

标准解决方案是递归解决方案，如下所示。

void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
}

这会遇到 O(n*n!)。这是我们能做的最好的，还是有什么办法可以让它更快？

Answer 1

您可以使用 std::next_permutation。请注意，它仅适用于排序数组。
这个解决方案的优点:1)是标准的2) 是非递归的

这是一个例子(http://www.cplusplus.com/reference/algorithm/next_permutation/):

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1, 2, 3};

  std::sort (myints, myints + 3);

  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while (std::next_permutation (myints, myints + 3));

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}