Question

Generate all permutations of {3, 8, 2} by the Johnson-Trotter algorithm. Show the steps.

Answer 1

Dear Learner,

Here is the solution to your question.

Johnson-Trotter algorithm basically finds all the permutation of n numbers without going through all the shorter permutations. Furthermore, this algorithm generates the permutation just by swapping a pair of adjacent integers.

In this algorithm, we have directed integers which basically means the direction in which that particular integer will move or swap.Any such integer,which is greater than the next integer in it's direction is said to be 'mobile'. Next, we find the largest 'mobile number' of a series.

Later, as we move on, we will switch the direction of all the integers whose value is greater than the current 'mobile integer'

[NOTE: the '<' and '>' on the left of every integer is representing the direction in which that particular integer is going, and not the actual 'less than' or 'greater than']

To begin with, we first arrange the numbers in descending order

< 2 < 3 < 8

Above, the largest mobile number is 8, so we swap it with the next immediate integer i.e,. 3.

Since 8 is the current mobile number and also the largest, we don't need to change any directions

< 2 < 8 < 3

Again, since 8 is the mobile number we swap it with 2

< 8 < 2 < 3

Now,in the above line we can see that the current mobile number is 3 as it is greater than it's immediate integer and since 8(which is no longer mobile) is greater than 3 we will change its direction.

> 8 < 3 < 2

Now, again, 3 will be swapped withe the next number in its direction.

< 3 > 8 < 2

At last, 2 will be swapped with 8 giving us the final permutation

< 3 < 2 < 8

I hope I have answered the question the way you were expecting. If you still have any doubts or want any further explanation, fell free to ask us in the comment section.

Please leave a like if this was helpful.

Thanks,

Happy Studying.