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