提高给定的字符串的所有排列的时间复杂度 [英] Improving the time complexity of all permutations of a given string

问题描述

这个问题通常是冒充给出一个字符串，打印出它所有排列。对于如串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

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

这篇关于提高给定的字符串的所有排列的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！