# 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, $\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...!

3. ## Re: Systematic generation of all permutations

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