Results 1 to 3 of 3

Math Help - Systematic generation of all permutations

  1. #1
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273

    Systematic generation of all permutations

    Hey guys,
    I'm having trouble understanding what the "Systematic generation of all permutations" algorithm in wikipedia (here: Permutation - Wikipedia, the free encyclopedia) specifically does. The four steps are below.


    1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
    2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
    3. Swap a[k] with a[l].
    4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
    If anyone could just clarify this a little, would be great.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: Systematic generation of all permutations

    Quote Originally Posted by sfspitfire23 View Post
    Hey guys,
    I'm having trouble understanding what the "Systematic generation of all permutations" algorithm in wikipedia (here: Permutation - Wikipedia, the free encyclopedia) specifically does. The four steps are below.


    1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
    2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
    3. Swap a[k] with a[l].
    4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
    If anyone could just clarify this a little, would be great.

    Thanks
    I too am a tad confused - I can't get it to work!

    Firstly, < means "to the left of".

    So, a_1a_2a_3a_4 is our first permutation.

    Now, the largest integer k such that a_k<a_{k+1} is 3, and the largest i such that a_k<a_i is 4, so

    swapping a_k and a_i noting that step 4 doesn't do anything,

    a_1a_2a_4a_3 is our next permutation.

    Next, k=2, i=4 to get a_1a_4a_2a_3

    Next, k=2, i=3 to get a_1a_4a_3a_2

    Next, k=1, i=4 to get a_4a_1a_3a_2

    Next, k=1, i=3 to get a_4a_3a_1a_2

    Next, k=1, i=2 to get a_4a_3a_2a_1.

    There should be 4!=24 permutations! Although step 4 never comes into it with what I did...(I tried to see it it perhaps meant "including a[k+1]", but if you do this between a_1a_4a_2a_3 and a_1a_4a_3a_2 (so permutations 3 and 4) then permutation 4 is the same as permutation 3, which can't happen!)

    I have noticed wikipedia is often wrong when it comes to algorithms - I remember coming across an algorithm which it gave in pseudo code as well as in `proper' code. But these two versions of `the same' algorithm turned out to have vastly different efficiencies...!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273

    Re: Systematic generation of all permutations

    Hmm interesting. I need to stop relying on it so much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Systematic approach for multi variable limits?
    Posted in the Calculus Forum
    Replies: 5
    Last Post: December 18th 2011, 05:31 PM
  2. solve the system through systematic elimination...
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: March 27th 2011, 06:42 AM
  3. solve by systematic elimination...
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: March 23rd 2011, 12:03 AM
  4. Replies: 4
    Last Post: April 21st 2009, 09:38 AM

Search Tags


/mathhelpforum @mathhelpforum