Steinhaus Johnson Trotter

About the algorithm

Given a positive integer n, this algorithm generates a list of permutations of {1, … , n} in non-lexicographical order.

i.e. given an input of 3, this algorithm would output

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3

Terms used in this algorithm

Direction

First the numers 1…n are written in the increasing order and a direction is assigned to each of them which is initially LEFT. Note that the < symbol in front of each number below indicates that the direction associated with it is LEFT

<1 <2 <3

Similarly a number followed by > symbol would indicate that its direction is RIGHT. In the below example, number 3‘s direction is RIGHT.

3> <1 <2

Mobile integer

This algorithm uses a term called mobile integer. An integer is said to be mobile, if the adjacent number on its direction is smaller than this.

Note:-

If an integer is on the rightmost column pointing to the right, it’s not mobile.

If an integer is on the leftmost column pointing to the left, it’s not mobile.

The Algorithm

• 1. The algorithm works by placing the numbers 1…n in the increasing order and associating LEFT < as the direction for each of them

  2. Find the largest mobile integer and swap it with the adjacent element on its direction without changing the direction of any of these two.

  3. In doing so, if the largest mobile integer has reached a spot where it’s no more mobile, proceed with the next largest integer if it’s mobile (or with the next …). There’s a catch. Read step 4.

  4. After each swapping, check if there’s any number, larger than the current largest mobile integer. If there’s one or more, change the direction of all of them. (see the example shown bellow for clarity).

  5. The algorithm terminates when there are no more mobile integers.

The Algorithm in action

1. <1 <2 <3 2. <1 <3 <2 3. <3 <1 <2

Now 3 is no longer mobile as it’s in the leftmost column pointing to the left. Therefore proceed with the next largest mobile integer which is 2.

4. 3> <2 <1

Now, number 3 has changed it’s direction due to step (iv) of the algorithm stated above. After three iterations in this step, as shown, when <2 was swapped with <1, the algorithm checks to see if there’s any number (not only mobile integers) larger than 2. Because there’s <3, it’s direction gets changed making it 3>

The algorithm now proceeds with 3> as it’s become the largest mobile integer again.

5. <2 3> <1 6. <2 <1 3>

The algorithm terminates now as none of the integers are mobile any longer. The reason as to why they are not mobile is explained below.

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

<1 is no longer mobile as there are no numbers on its direction smaller than itself.

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

Therefore the algorithm generates permutations in the non-lexicographical order as shown in steps 1 through6 above.

Shown below is an example with n=4.

1. <1 <2 <3 <4 2. <1 <2 <4 <3 3. <1 <4 <2 <3 4. <4 <1 <2 <3

<4 is no longer mobile as it’s on the leftmost column pointing to the left. Swap <3 with <2 and change4‘s direction to 4>

5. 4> <1 <3 <2 6. <1 4> <3 <2 7. <1 <3 4> <2 8. <1 <3 <2 4>

4> is no longer mobile as it’s on the rightmost column pointing to the right. Swap <3 with <1 and change 4‘s direction to <4

9. <3 <1 <2 <4 10. <3 <1 <4 <2 11. <3 <4 <1 <2 12. <4 <3 <1 <2

<4 is no longer mobile as it’s on the leftmost column pointing to the left

<3 is no longer mobile now as there’s no number smaller than itself on it’s direction

swap <2 with <1 and

(a)change 4‘s direction to 4>

(b)change 3‘s direction to 3>

Note that when a number is swapped, the direction of all those numbers that are larger than this number has to be changed

13. 4> 3> <2 <1 14. 3> 4> <2 <1 15. 3> <2 4> <1 16. 3> <2 <1 4>

4 is no longer mobile as it’s on the rightmost column pointing to the right. Swap 3> with <2 and change4‘s direction to <4

17. <2 3> <1 <4 18. <2 3> <4 <1 19. <2 <4 3> <1 20. <4 <2 3> <1

4 is no longer mobile as it’s on the leftmost column pointing to the left. Swap 3> with <1 and change 4‘s direction to 4>

21. 4> <2 <1 3> 22. <2 4> <1 3> 23. <2 <1 4> 3> 24. <2 <1 3> 4>

No numbers are mobile anymore (I hope you can understand why. If not, leave a comment and I’ll explain it too) and therefore the algorithm terminates after having generated 4!=24 permutations.

Snippet

1. // Coded by EricR2427

2. #include <iostream>

3. #include <vector>

4. #include <algorithm>

5. using namespace std;

6. class permutations {

7. public:

8. permutations(int n);

9. void printPermutations();

10. private:

11. bool isMobile();

12. bool isMobile(int p);

13. int findLargest();

14. void printData();

15. vector<int> digits;

16. vector<int> directions;

17. };

18. int main(int argc, char *argv[]) {

19. int x;

20. cout << "Print permutations for how many numbers? ";

21. cin >> x;

22. permutations per(x);

23. per.printPermutations();

24. }

25. permutations::permutations(int n) { // constructor - fills the vectors

26. for (int i = 1; i <= n; i++) {

27. digits.push_back(i);

28. directions.push_back(0);

29. }

30. }

31. void permutations::printPermutations() { // main function - finds and prints all permutations using the other functions

32. int k, count = 1;

33. printData();

34. while(isMobile()) {

35. k = findLargest();

36. if (directions[k] == 0) {

37. swap(digits[k], digits[k-1]);

38. swap(directions[k], directions[k-1]);

39. k -= 1;

40. }

41. else {

42. swap(digits[k], digits[k+1]);

43. swap(directions[k], directions[k+1]);

44. k += 1;

45. }

46. for (int i = 0; i < digits.size(); i++) {

47. if (digits[i] > digits[k]) {

48. if (directions[i] == 0) {

49. directions[i] = 1;

50. }

51. else {

52. directions[i] = 0;

53. }

54. }

55. }

56. printData();

57. count++;

58. }

59. cout << "Total permutations: " << count << endl;

60. }

61. bool permutations::isMobile() { // checks to see if any elements are mobile

62. for (int i = 0; i < digits.size(); i++) {

63. if (isMobile(i)) {

64. return true;

65. }

66. }

67. return false;

68. }

69. bool permutations::isMobile(int p) { // finds if an element is mobile

70. if (p == 0 && directions[p] == 0) {

71. return false;

72. }

73. else if (p == digits.size()-1 && directions[p] == 1) {

74. return false;

75. }

76. else {

77. if (directions[p] == 0) {

78. if (digits[p] > digits[p-1]) {

79. return true;

80. }

81. }

82. else {

83. if (digits[p] > digits[p+1]) {

84. return true;

85. }

86. }

87. }

88. return false;

89. }

90. int permutations::findLargest() { // finds the largest mobile number

91. vector<int> mobileNumbers;

92. for (int i = 0; i < digits.size(); i++) {

93. if (isMobile(i)) {

94. mobileNumbers.push_back(i);

95. }

96. }

97. int largest = mobileNumbers[0];

98. for (int p = 1; p < mobileNumbers.size(); p++) {

99. if (digits[mobileNumbers[p]] > digits[largest]) {

100. largest = mobileNumbers[p];

101. }

102. }

103. return largest;

104. }

105. void permutations::printData() { // prints out the current order

106. for (int i = 0; i < digits.size(); i++) {

107. cout << digits[i] << " ";

108. }

109. cout << endl;

110. }