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

本文介绍了提高给定的字符串的所有排列的时间复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这个问题通常是冒充给出一个字符串，打印出它所有排列。对于如串ABC的排列是ABC，ACB，BAC，BCA，CAB，CBA。

The problem is generally posed as given a string, print all permutations of it. For eg, the permutations of string ABC are ABC, ACB, BAC, BCA, CAB, CBA.

的标准溶液是递归的，在下面给出。

The standard solution is a recursive one, given below.

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！）。这是我们能做的最好的或者是有某种方式使这个更快？

This, runs into O(n*n!). Is this the best we can do or is there someway to make this faster?

推荐答案

您可以使用的std :: next_permutation 。请注意它正常工作只在排序的数组。 这个解决方案优点： 1）它是标准 2）它是非递归

You can use std::next_permutation. Please, notice it works correctly only on sorted array. Good points about this solution: 1) It is standard 2) It is non-recursive

下面是一个例子（ www.cplusplus/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; }