how could we find out the permutation of given set of numbers

ok guys i was trying to solve this problem ie if we have 7,8,9 in an array then we should get {7,8,9}
{7,9,8} {8,7,9} {8,9,7} {9,8,7} {9,7,8} similarly for 5,6,7,8 digit numbers. The way i found to solve it was through tree traversal ie we find in-order, post-order, pre-order in taken only 3 bits at a time (ie if 7123 is given then find in,post,pre of 712 then of 123 and the numbers taking left number fixed so the repeated cases would be ignored) i use 3 bits at a time because the traversal only gave all combination for 3 digits. So implementing this was complex i implemented it for 3 digits but above 4 was tough. So can anyone can give me program to find out all permutation or can they implement my concept would be appreciated. DANKE

3 Likes

You can use Johnson-Trotter algorithm
http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml

This could be solved via backtracking. This is a working implementation.

Time complexity: O(n*n!)

@dreamwarrior12: if you are coding in C/C++ look at next_permutation function, this is exactly what you are looking for :wink:

i saw the algorithm but can u implement it would take a huge space as i think

2 Likes