查找字符串的所有可能排列

Question

我有一个程序，用于查找字符串所有可能的排列组合。

#include <stdio.h>

 /* Function to swap values at two pointers */
 void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
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
       }
   }
}

/* Driver program to test above functions */
int main()
{
   char a[] = "abcd";
   permute(a, 0, 3);
   getchar();
   return 0;
}

我想知道是否有更好的方法（更高效）来查找所有排列，因为该算法效率为O(n^n)。

谢谢.. :-)

- Gokul

---

为什么不使用std::next_permutation函数？ - Mohit Jain

我假设你正在使用 C 语言，而不是 C++（尽管你标记了额外的标签）。否则，你可以直接使用 <algorithm> 库中的 std::next_permutation 函数。 - Cory Kramer

如果您实际上使用的是C而不是C ++，则可以将此处的代码[https://dev59.com/92gu5IYBdhLWcg3wOUm-]调整为C代码。该帖子介绍了如何实现next_permutation函数。 - NathanOliver

Answer 1

这是标准中的内容。

#include<algorithm>
std::vector<int> vec;
std::next_permutation(std::begin(vec), std::end(vec));

在字符串情况下

# include<string>
#include<algorithm>

std::string str ="abcd"
do{
     std::cout<<str<<"\n";

} while(std::next_permutation(std::begin(str), std::end(str)));

- Steephen

---

我可以打赌我的早晨咖啡，OP正在使用C语言，且没有任何理由添加C++标签。 - Cory Kramer

Answer 2

没有比O(n * n!)更快的算法，因为你必须枚举所有的n!个可能性，每次处理n个字符。

你的算法也在O(n * n!)复杂度下运行，可以在http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/中看到。

- user4233758

---

如果您想要实际输出每个排列，那么无法打败O(n * n!)，但事实上您可以更快地生成它们，只需使用一个单一的交换操作即可从当前排列生成下一个排列。链接是：https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm。使用Even的加速，总体时间复杂度只需O(n!)。 - j_random_hacker