What's an algorithm to print the permutations of a string with much efficiency?

Question

The algorithm which I know is the below but why I hate this approach is it's time complexity is O((n+1)!) too worse in case of large strings

Start by sorting the string and printing that as the first permutation.
Now, we can find the next permutation as follows:

Let i be the last index such that input[i] < input[i + 1]. If there is no such index, then we’re done. Let j be the last index such that input[i] < input[j]. Swap input[i] with input[j]. Reverse input[i + 1] through input[input.length - 1].

Is there any better approach than the above one ?(If explanation is through code then please consider c or c++)... just I am expecting a better algorithm with lesser time complexity than the above one

see this http://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string — Gaurav Sehgal, Jul 03 '15 at 14:31

Xiaotian Pei · Answer 1 · 2015-07-03T18:09:35.650

6

There are n! permutations for a string with length n. Simply printing them is O(n * n!), how can you expect it will be much more efficient?

edited Jul 03 '15 at 18:09

answered Jul 03 '15 at 14:34

Xiaotian Pei

3,210
21
40

Unless there are duplicate letters, then there are less than `n!` permutations. – Lundin Jul 03 '15 at 14:35
ya ,I know that but I had some hope, may be there can be any chances of getting much better one. – nikhil ponnuru Jul 03 '15 at 14:36
It's actually O(n*n!), since each print is itself O(n) – amit Jul 03 '15 at 16:00
@amit, thank you for the correction. – Xiaotian Pei Jul 03 '15 at 18:09

score 3 · Answer 2 · answered Jul 03 '15 at 14:39

Even the standard C++ implementation to print permutations of a string follows exactly same algorithm (std::next_permutation and std::prev_permutation)

std::string s;
std::sort(s.begin(), s.end());
do {
    std::cout << s << std::endl;
} while(std::next_permutation(s.begin(), s.end()));

score 0 · Answer 3 · answered Jul 03 '15 at 14:39

0

Keep in mind that in C++ the STL has std::next_permutation that does the job you need

answered Jul 03 '15 at 14:39

marom

5,064
10
14

What's an algorithm to print the permutations of a string with much efficiency?

3 Answers3