1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Brain Teaser

  1. Feb 25, 2007 #1
    Brain Teaser!!

    This algorithm lists all permutations of {1,2 .....n} in increasing lexicographic order.
    Input: n
    Output: All permutations of {1,2....n} in increasing lexicographic order.





    1. permutation(n){
    2. for i = 1 to n
    3. Si = i
    4. println(S1....Sn)// print the first premutation
    5. for i = 2 to n! {
    6. m=n-1
    7. while(Sm > Sm+1)
    8. //find the first decrease working from the right
    9. m = m-1
    10. k=n
    11. while(Sm > Sk)
    12. //find right most element Sk with Sm < Sk
    13. K = K-1
    14. swap (Sm,Sk)
    15. p=m+1
    16. q = n
    17. while (p<q) {
    18. //swap Sm+1 and Sn, swap Sm+2 and Sn-1 and so on
    19. swap(Sp,Sq)
    20. p = p+1
    21. q = q -1
    22. }
    23. println(S1,....Sn)// Print the ith permutation
    24. }
    25. }





    When n=3


    This was so much fun, I thought I would share it with y'all!
    RSF!:rofl:
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?