Question

i want to know how johnson-trotter algorithm works. easy explaination please .

Answer 1

Given a sequence of numbers from 1 to n.

each permutation in the sequence we need to generate that would differ from the previous permutation by just swapping two adjacent elements in sequence.

permutation of two elements:

1 2 and 2 1

permutation of three elements:

1 2 3, 1 3 2, 3 1 2, 2 1 3,2 3 1, 3 2 1

terms used in algorithm:

Direction: first the numbers 1 to n are written in increasing order.

initially left direction assigned to each of them.

< symbol indicates that the direction associated with it is left.(<1 )

> symbol indicates that the direction associated with it is right.(>3)

Mobile integer: an integer said to be mobile if adjacent number on its direction is smaller than this.

if integer is on the leftmost column pointing to the left, it is not mobile.

if integer is on the rightmost column,pointing to the right, it is not mobile.

Johnson-Trotter Algorithm:

1) placing the numbers 1 to n in increasing order and each of them associated with left direction initially.

2) find the largest mobile integer and swap it with adjacent element on its direction without changing direction of both.

3) In doing this if largest mobile integer has reached a spot,where it's no more mobile, proceed with next largest integer if it is mobile.

4) after swapping check is there any number which is larger then current largest mobile integer,it there is one or more then change the direction of all of them.

5) algorithm terminate when there are no more mobile integer.

Example:

<1 <2 <3

largest mobile integer is 3. we swap 2 and 3. since 3 is largest so we don't change any direction.

<1 <3 <2

largest mobile integer is 3 not 2 because adjacent element of 2 in its direction is 3 which is not smaller than 2.

swap 1 and 3.

<3 <1 <2

now 3 is no longer mobile as it is in leftmost column pointing to left. so proceed with next largest mobile integer which is 2.

swap 1 and 2.

algorithm check is there any number which is larger then current largest mobile integer(in this case yes) if it is then change its direction.

>3 <2 <1

now proceed with >3 as its largest mobile integer again.

swap 2 and 3

<2 >3 <1

swap 3 and 1

<2 <1 >3

algorithm terminates because none of integer are mobile any longer.

>3 is no longer mobile because as it is on the rightmost column pointing to right.

<2 is no longer mobile because as it is on the leftmost column pointing to left.

<1 is not mobile because no numbers on its direction which are smaller than this.