# Thread: Systematic generation of all permutations

1. ## 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

2. ## Re: Systematic generation of all permutations

Originally Posted by sfspitfire23
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 is 3, and the largest i such that $a_k 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...!

3. ## Re: Systematic generation of all permutations

Hmm interesting. I need to stop relying on it so much!