fastest runtime to print all permutations

Question

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).

Answer 1

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.