0

I am trying to write a function to print all permutations of numbers 1 to n. I saw a lot of C++ codes to do this, But I do not know which one has the most optimal time.

Please answer to this question only if you have this function's C++ code with fastest runtime.

Sample test :

input:

3

output:

123

132

213

231

312

321

please help me to generate this function(Definitely with the fastest runtime).

Amirhossein Mahdinejad
  • 574
  • 2
  • 8
  • 23
  • I think by fastes algorithm you did mean program with fastest runtime not complexity. so you really want just performance optimizations not algorithm changes. the fastest way is usually to avoid overhead and recursion (in C++ like languages) for functional programing is the opposite (recursion is the fastest there) ... The best for the first case are raw-coded nested loops , then iterationaly nested loop (simulation of recursion by twoo loops) and then the recursion version. also try to minimize calling/returning parameters number to minimum. – Spektre Mar 15 '14 at 09:22

1 Answers1

2

Your output contains n! lines with n numbers, so you can not get better complexity than O(n*n!). And the most obvious, brute force algorithm does it with that complexity. So, despite you did not include the c++ code you saw, I bet it runs in O(n*n!) time, which is optimal.

EDIT: Corrected, thanks to comments.

Bartosz Marcinkowski
  • 6,651
  • 4
  • 39
  • 69
  • 2
    This is wrong sing printing a permutation is `O(n)` so the complexity is O(n*n!). – hivert Mar 15 '14 at 09:12
  • @hivert I dont think so ... look the items are not repeated so it is n! (there is no 111,112,113,...). – Spektre Mar 15 '14 at 09:16
  • 1
    It's not a question of repetition. Printing a permutation of `[1...n]` that is `n` characters is obviously a `O(n)` operation. – hivert Mar 15 '14 at 09:19
  • I agree with @hivert. Moreover, there will be `n!` distinct permutations in the worst case, but in every step of the recursion, another loop runs to check if an item has already been used or not, if not then assign that and call recursion. So obviously it's `O(n * n!)` IMHO – Fallen Mar 15 '14 at 09:31
  • @Fallen: Your moreover is not quite true. Using [Johnson-Trotter](http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm) algorithm you can compute in place the next permutation in `O(1)` if you allows for a different order that the OP's – hivert Mar 15 '14 at 09:33
  • Does Johnson-Trotter algorithm ensure lexicographcially sorted permutations? I don't think so @hivert – Fallen Mar 15 '14 at 09:36
  • I said "if you allows for a different order that the OP's"... – hivert Mar 15 '14 at 09:36
  • oh got it. I think that link adds more value to this question + discussion :-) – Fallen Mar 15 '14 at 09:38