-4

I want to generate all possible permutations of a given string in C++.

I read this discussion here on StackOverflow only: How to generate all permutations of an array in sorted order?

The answer's fine but once I get moving to say a string of 12-14 characters the program takes considerable amount of time.

Is there a better way to solve this such that it doesn't take more than a few seconds?

Given I have a string of say 10 characters.

Community
  • 1
  • 1
Sanskar Katiyar
  • 7
  • 6
  • 1
    I think if std::next_permutation could be made faster, they would have made it that way. – Abhishek Bansal Dec 06 '13 at 14:14
  • 3
    Well, yeah. Of course it takes a considerable amount of time. It's an `O(n(n!))` problem. And `12!` is over 400 million. Even if finding the next permutation was magically `O(1)`, it would still be an `O(n!)` problem. – Benjamin Lindley Dec 06 '13 at 14:14
  • Yes. That is the big problem. – Sanskar Katiyar Dec 06 '13 at 14:23
  • So answer is just "no". Not tremendously faster, maybe if there is an optimisation in the code, you would gain by a constant factor , but when you're speaking of factorial complexity, factor are mostly negligeable. – Johan Dec 06 '13 at 14:26
  • @SanskarKatiyar: Indeed; so big that current hardware can't do anything about it. If you want to generate `n!` sequences, then you'll need to do some multiple of `n!` operations, and there are limits to how much they can be parallelised. Quantum processors or self-replicating nano-machines might help, but they'll have to be invented first. – Mike Seymour Dec 06 '13 at 14:27
  • @BenjaminLindley the funny thing is that for some applications, 400 million isn't all that much. We all have gigahz processors so we can get millions of things in less than a second if we can do it fast enough. Granted this solution to the permutations is not scalable by the growth, but just because a problem is big growth doesn't mean we can't do it efficiently for small values. The real question is, 1) do you actually need all the permutations (X vs Y problem)? and 2) how fast is fast for 10 characters? – IdeaHat Dec 06 '13 at 14:28
  • If time is the issue - sometimes using a c style strings (char*) is more efficient than using a c++ string. – amit Dec 06 '13 at 14:30
  • Why do you need to get all permutation? Are you searching for the "best" permutation? That we may be able to get significantly faster. Getting all permutations however...you'll be SOL. – IdeaHat Dec 06 '13 at 14:35
  • @SanskarKatiyar This question itself states that you didnt understand the concept. The lower bound of any algorithm is the time needed to state the output and you cannot do better than O(N!). – Vikram Bhat Dec 06 '13 at 15:23

2 Answers2

1

I don't think you can achieve better than std::next_permutation

std::sort( myString.begin(), myString.end() );

do {
  std::cout << myString;
} while ( std::next_permutation( myString.begin(), myString.end() ) );
Abhishek Bansal
  • 12,447
  • 4
  • 29
  • 44
0

If you do not need the permutations in lexicographic (sorted) order, then you can get your next permutation from a given one with just swapping two adjacent elements in your array. Basically, instead of O(n * n!) with std:next_permutation(), you can traverse all permutations in O(n!).

These kind of algorithms are called Generation with minimal changes.

Since you need all permutations, your output and the whole solution will be at least O(n!). So, algorithmically the best you can get is O(n!), so I would suggest looking into optimizations of your implementations: utilize parallel computing, low-level programming languages, compiler/architecture optimizations, etc.

ile
  • 339
  • 1
  • 7