Results 1 to 3 of 3

Thread: 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, $\displaystyle a_1a_2a_3a_4$ is our first permutation.

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

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

    $\displaystyle a_1a_2a_4a_3$ is our next permutation.

    Next, k=2, i=4 to get $\displaystyle a_1a_4a_2a_3$

    Next, k=2, i=3 to get $\displaystyle a_1a_4a_3a_2$

    Next, k=1, i=4 to get $\displaystyle a_4a_1a_3a_2$

    Next, k=1, i=3 to get $\displaystyle a_4a_3a_1a_2$

    Next, k=1, i=2 to get $\displaystyle 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 $\displaystyle a_1a_4a_2a_3$ and $\displaystyle 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: Dec 18th 2011, 05:31 PM
  2. solve the system through systematic elimination...
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: Mar 27th 2011, 06:42 AM
  3. solve by systematic elimination...
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: Mar 23rd 2011, 12:03 AM
  4. Replies: 4
    Last Post: Apr 21st 2009, 09:38 AM

Search Tags


/mathhelpforum @mathhelpforum