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
The algorithm works by placing the numbers 1…n in the increasing order and associating LEFT < as the direction for each of them
Find the largest mobile integer and swap it with the adjacent element on its direction without changing the direction of any of these two.
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.
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).
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
// Coded by EricR2427
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class permutations {
public:
permutations(int n);
void printPermutations();
private:
bool isMobile();
bool isMobile(int p);
int findLargest();
void printData();
vector<int> digits;
vector<int> directions;
};
int main(int argc, char *argv[]) {
int x;
cout << "Print permutations for how many numbers? ";
cin >> x;
permutations per(x);
per.printPermutations();
}
permutations::permutations(int n) { // constructor - fills the vectors
for (int i = 1; i <= n; i++) {
digits.push_back(i);
directions.push_back(0);
}
}
void permutations::printPermutations() { // main function - finds and prints all permutations using the other functions
int k, count = 1;
printData();
while(isMobile()) {
k = findLargest();
if (directions[k] == 0) {
swap(digits[k], digits[k-1]);
swap(directions[k], directions[k-1]);
k -= 1;
}
else {
swap(digits[k], digits[k+1]);
swap(directions[k], directions[k+1]);
k += 1;
}
for (int i = 0; i < digits.size(); i++) {
if (digits[i] > digits[k]) {
if (directions[i] == 0) {
directions[i] = 1;
}
else {
directions[i] = 0;
}
}
}
printData();
count++;
}
cout << "Total permutations: " << count << endl;
}
bool permutations::isMobile() { // checks to see if any elements are mobile
for (int i = 0; i < digits.size(); i++) {
if (isMobile(i)) {
return true;
}
}
return false;
}
bool permutations::isMobile(int p) { // finds if an element is mobile
if (p == 0 && directions[p] == 0) {
return false;
}
else if (p == digits.size()-1 && directions[p] == 1) {
return false;
}
else {
if (directions[p] == 0) {
if (digits[p] > digits[p-1]) {
return true;
}
}
else {
if (digits[p] > digits[p+1]) {
return true;
}
}
}
return false;
}
int permutations::findLargest() { // finds the largest mobile number
vector<int> mobileNumbers;
for (int i = 0; i < digits.size(); i++) {
if (isMobile(i)) {
mobileNumbers.push_back(i);
}
}
int largest = mobileNumbers[0];
for (int p = 1; p < mobileNumbers.size(); p++) {
if (digits[mobileNumbers[p]] > digits[largest]) {
largest = mobileNumbers[p];
}
}
return largest;
}
void permutations::printData() { // prints out the current order
for (int i = 0; i < digits.size(); i++) {
cout << digits[i] << " ";
}
cout << endl;
}