Johnson and Trotter algorithm
We are given a sequence of numbers from 1 to n. Each permutation in the sequence that we need to generate should differ from the previous permutation by swapping just two adjacent elements of the sequence. Examples:
Input : n = 3 Output : 123 132 312 321 231 213 Input : n = 4 Output : 1234 1243 1423 4123 4132 1432 1342 1324 3124 3142 3412 4312 4321 3421 3241 3214 2314 2341 2431 4231 4213 2413 2143 2134
A simple solution to use permutations of n-1 elements to generate permutations of n elements. For example let us see how to generate permutations of size 3 using permutations of size 2. Permutations of two elements are 1 2 and 2 1. Permutations of three elements can be obtained by inserting 3 at different positions in all permutations of size 2. Inserting 3 in different positions of 1 2 leads to 1 2 3, 1 3 2 and 3 1 2. Inserting 3 in different positions of 2 1 leads to 2 1 3, 2 3 1 and 3 2 1. To generate permutations of size four, we consider all above six permutations of size three and insert 4 at different positions in every permutation. Johnson and Trotter algorithm The Johnson and Trotter algorithm doesn’t require to store all permutations of size n-1 and doesn’t require going through all shorter permutations. Instead, it keeps track of the direction of each element of the permutation.
- Find out the largest mobile integer in a particular sequence. A directed integer is said to be mobile if it is greater than its immediate neighbor in the direction it is looking at.
- Switch this mobile integer and the adjacent integer to which its direction points.
- Switch the direction of all the elements whose value is greater than the mobile integer value.
- Repeat the step 1 until unless there is no mobile integer left in the sequence.
Let us see how to generate permutations of size four. We first print 1 2 3 4. Initially all directions are right to left. <1 <2 <3 <4 All mobile numbers are 2, 3 and 4. The largest mobile number is 4. We swap 3 and 4. Since 4 is largest, we don't change any direction. <1 <2 <4 <3 4 is the largest mobile. We swap it with 2. <1 <4 <2 <3 4 is the largest mobile. We swap it with 1. <4 <1 <2 <3 [Iteration #4] 3 is largest mobile. We swap it with 2 and change directions of greater elements. 4> <1 <3 <2 4 is largest mobile. We swap it with 1. <1 4> <3 <2 4 is largest mobile. We swap it with 3. <1 <3 4> <2 4 is largest mobile. We swap it with 2. <1 <3 <2 4> [Iteration #8] 3 is largest mobile. We swap it with 1 and change directions of greater elements. <3 <1 <2 <4 4 is largest mobile. We swap it with 2. <3 <1 <4 <2 4 is largest mobile. We swap it with 1. <3 <4 <1 <2 4 is largest mobile. We swap it with 3. <4 <3 <1 <2 [Iteration #12] 2 is largest mobile. We swap it with 1 and change directions of greater elements. 4> 3> <2 <1 ..The three next swaps with 4 as largest mobile result in: 3> <2 <1 4> [Iteration #16] 3 is largest mobile. We swap it with 2 and change directions of greater elements. <2 3> <1 <4 ..The three next swaps with 4 as largest mobile result in: <4 <2 3> <1 [Iteration #20] 3 is largest mobile. We swap it with 1 and change directions of greater elements. 4> <2 <1 3> ..The three next swaps with 4 as largest mobile result in: <2 <1 3> 4> [Iteration #24] There is no mobile integer left.
Below is the implementation of the approach.
C++
// CPP program to print all permutations using // Johnson and Trotter algorithm. #include <bits/stdc++.h> using namespace std; bool LEFT_TO_RIGHT = true ; bool RIGHT_TO_LEFT = false ; // Utility functions for finding the // position of largest mobile integer in a[]. int searchArr( int a[], int n, int mobile) { for ( int i = 0; i < n; i++) if (a[i] == mobile) return i + 1; } // To carry out step 1 of the algorithm i.e. // to find the largest mobile integer. int getMobile( int a[], bool dir[], int n) { int mobile_prev = 0, mobile = 0; for ( int i = 0; i < n; i++) { // direction 0 represents RIGHT TO LEFT. if (dir[a[i] - 1] == RIGHT_TO_LEFT && i != 0) { if (a[i] > a[i - 1] && a[i] > mobile_prev) { mobile = a[i]; mobile_prev = mobile; } } // direction 1 represents LEFT TO RIGHT. if (dir[a[i] - 1] == LEFT_TO_RIGHT && i != n - 1) { if (a[i] > a[i + 1] && a[i] > mobile_prev) { mobile = a[i]; mobile_prev = mobile; } } } if (mobile == 0 && mobile_prev == 0) return 0; else return mobile; } // Prints a single permutation int printOnePerm( int a[], bool dir[], int n) { int mobile = getMobile(a, dir, n); int pos = searchArr(a, n, mobile); // swapping the elements according to the // direction i.e. dir[]. if (dir[a[pos - 1] - 1] == RIGHT_TO_LEFT) swap(a[pos - 1], a[pos - 2]); else if (dir[a[pos - 1] - 1] == LEFT_TO_RIGHT) swap(a[pos], a[pos - 1]); // changing the directions for elements // greater than largest mobile integer. for ( int i = 0; i < n; i++) { if (a[i] > mobile) { if (dir[a[i] - 1] == LEFT_TO_RIGHT) dir[a[i] - 1] = RIGHT_TO_LEFT; else if (dir[a[i] - 1] == RIGHT_TO_LEFT) dir[a[i] - 1] = LEFT_TO_RIGHT; } } for ( int i = 0; i < n; i++) cout << a[i]; cout << " " ; } // To end the algorithm for efficiency it ends // at the factorial of n because number of // permutations possible is just n!. int fact( int n) { int res = 1; for ( int i = 1; i <= n; i++) res = res * i; return res; } // This function mainly calls printOnePerm() // one by one to print all permutations. void printPermutation( int n) { // To store current permutation int a[n]; // To store current directions bool dir[n]; // storing the elements from 1 to n and // printing first permutation. for ( int i = 0; i < n; i++) { a[i] = i + 1; cout << a[i]; } cout << endl; // initially all directions are set // to RIGHT TO LEFT i.e. 0. for ( int i = 0; i < n; i++) dir[i] = RIGHT_TO_LEFT; // for generating permutations in the order. for ( int i = 1; i < fact(n); i++) printOnePerm(a, dir, n); } // Driver code int main() { int n = 4; printPermutation(n); return 0; } |
Java
// Java program to print all // permutations using Johnson // and Trotter algorithm. import java.lang.*; import java.util.*; public class GfG { private final static boolean LEFT_TO_RIGHT = true ; private final static boolean RIGHT_TO_LEFT = false ; // Utility functions for // finding the position // of largest mobile // integer in a[]. public static int searchArr( int a[], int n, int mobile) { for ( int i = 0 ; i < n; i++) if (a[i] == mobile) return i + 1 ; return 0 ; } // To carry out step 1 // of the algorithm i.e. // to find the largest // mobile integer. public static int getMobile( int a[], boolean dir[], int n) { int mobile_prev = 0 , mobile = 0 ; for ( int i = 0 ; i < n; i++) { // direction 0 represents // RIGHT TO LEFT. if (dir[a[i] - 1 ] == RIGHT_TO_LEFT && i != 0 ) { if (a[i] > a[i - 1 ] && a[i] > mobile_prev) { mobile = a[i]; mobile_prev = mobile; } } // direction 1 represents // LEFT TO RIGHT. if (dir[a[i] - 1 ] == LEFT_TO_RIGHT && i != n - 1 ) { if (a[i] > a[i + 1 ] && a[i] > mobile_prev) { mobile = a[i]; mobile_prev = mobile; } } } if (mobile == 0 && mobile_prev == 0 ) return 0 ; else return mobile; } // Prints a single // permutation public static int printOnePerm( int a[], boolean dir[], int n) { int mobile = getMobile(a, dir, n); int pos = searchArr(a, n, mobile); // swapping the elements // according to the // direction i.e. dir[]. if (dir[a[pos - 1 ] - 1 ] == RIGHT_TO_LEFT) { int temp = a[pos - 1 ]; a[pos - 1 ] = a[pos - 2 ]; a[pos - 2 ] = temp; } else if (dir[a[pos - 1 ] - 1 ] == LEFT_TO_RIGHT) { int temp = a[pos]; a[pos] = a[pos - 1 ]; a[pos - 1 ] = temp; } // changing the directions // for elements greater // than largest mobile integer. for ( int i = 0 ; i < n; i++) { if (a[i] > mobile) { if (dir[a[i] - 1 ] == LEFT_TO_RIGHT) dir[a[i] - 1 ] = RIGHT_TO_LEFT; else if (dir[a[i] - 1 ] == RIGHT_TO_LEFT) dir[a[i] - 1 ] = LEFT_TO_RIGHT; } } for ( int i = 0 ; i < n; i++) System.out.print(a[i]); System.out.print( " " ); return 0 ; } // To end the algorithm // for efficiency it ends // at the factorial of n // because number of // permutations possible // is just n!. public static int fact( int n) { int res = 1 ; for ( int i = 1 ; i <= n; i++) res = res * i; return res; } // This function mainly // calls printOnePerm() // one by one to print // all permutations. public static void printPermutation( int n) { // To store current // permutation int [] a = new int [n]; // To store current // directions boolean [] dir = new boolean [n]; // storing the elements // from 1 to n and // printing first permutation. for ( int i = 0 ; i < n; i++) { a[i] = i + 1 ; System.out.print(a[i]); } System.out.print( "\n" ); // initially all directions // are set to RIGHT TO // LEFT i.e. 0. for ( int i = 0 ; i < n; i++) dir[i] = RIGHT_TO_LEFT; // for generating permutations // in the order. for ( int i = 1 ; i < fact(n); i++) printOnePerm(a, dir, n); } // Driver function public static void main(String argc[]) { int n = 4 ; printPermutation(n); } } // This code is contributed by Sagar Shukla |
Python3
# Python program to print all permutations # using Johnson and Trotter algorithm. LEFT_TO_RIGHT = True RIGHT_TO_LEFT = False # Utility functions for finding the # position of largest mobile integer in a[]. def searchArr(a, n, mobile): for i in range (n): if a[i] = = mobile: return i + 1 # To carry out step 1 of the algorithm i.e. # to find the largest mobile integer. def getMobile(a, dir , n): mobile_prev = 0 mobile = 0 for i in range (n): # direction 0 represents RIGHT TO LEFT. if dir [a[i] - 1 ] = = RIGHT_TO_LEFT and i ! = 0 : if a[i] > a[i - 1 ] and a[i] > mobile_prev: mobile = a[i] mobile_prev = mobile # direction 1 represents LEFT TO RIGHT. if dir [a[i] - 1 ] = = LEFT_TO_RIGHT and i ! = n - 1 : if a[i] > a[i + 1 ] and a[i] > mobile_prev: mobile = a[i] mobile_prev = mobile if mobile = = 0 and mobile_prev = = 0 : return 0 else : return mobile # Prints a single permutation def printOnePerm(a, dir , n): mobile = getMobile(a, dir , n) pos = searchArr(a, n, mobile) # swapping the elements according to # the direction i.e. dir[] if dir [a[pos - 1 ] - 1 ] = = RIGHT_TO_LEFT: a[pos - 1 ], a[pos - 2 ] = a[pos - 2 ], a[pos - 1 ] elif dir [a[pos - 1 ] - 1 ] = = LEFT_TO_RIGHT: a[pos], a[pos - 1 ] = a[pos - 1 ], a[pos] # changing the directions for elements # greater than largest mobile integer for i in range (n): if a[i] > mobile: if dir [a[i] - 1 ] = = LEFT_TO_RIGHT: dir [a[i] - 1 ] = RIGHT_TO_LEFT elif dir [a[i] - 1 ] = = RIGHT_TO_LEFT: dir [a[i] - 1 ] = LEFT_TO_RIGHT for i in range (n): print (a[i], end = '') print ("") # To end the algorithm for efficiency it ends # at the factorial of n because number of # permutations possible is just n!. def fact(n): res = 1 for i in range ( 1 , n + 1 ): res = res * i return res # This function mainly calls printOnePerm() # one by one to print all permutations. def printPermutation(n): # To store current permutation # storing the elements from 1 to n and a = [i + 1 for i in range (n)] # Printing the first permutation for i in range (n): print (a[i], end = '') print ("") # To store current directions # initially all directions are set # to RIGHT TO LEFT i.e. 0. dir = [RIGHT_TO_LEFT for i in range (n)] # for generating permutations in the order. for i in range ( 1 , fact(n)): printOnePerm(a, dir , n) # Driver code n = 4 printPermutation(n) # This Code is Contributed by Prasad Kandekar(prasad264) |
C#
// Java program to print all // permutations using Johnson // and Trotter algorithm. using System; public class GfG { private static bool LEFT_TO_RIGHT = true ; private static bool RIGHT_TO_LEFT = false ; // Utility functions for // finding the position // of largest mobile // integer in a[]. public static int searchArr( int [] a, int n, int mobile) { for ( int i = 0; i < n; i++) if (a[i] == mobile) return i + 1; return 0; } // To carry out step 1 // of the algorithm i.e. // to find the largest // mobile integer. public static int getMobile( int [] a, bool [] dir, int n) { int mobile_prev = 0, mobile = 0; for ( int i = 0; i < n; i++) { // direction 0 represents // RIGHT TO LEFT. if (dir[a[i] - 1] == RIGHT_TO_LEFT && i != 0) { if (a[i] > a[i - 1] && a[i] > mobile_prev) { mobile = a[i]; mobile_prev = mobile; } } // direction 1 represents // LEFT TO RIGHT. if (dir[a[i] - 1] == LEFT_TO_RIGHT && i != n - 1) { if (a[i] > a[i + 1] && a[i] > mobile_prev) { mobile = a[i]; mobile_prev = mobile; } } } if (mobile == 0 && mobile_prev == 0) return 0; else return mobile; } // Prints a single // permutation public static int printOnePerm( int [] a, bool [] dir, int n) { int mobile = getMobile(a, dir, n); int pos = searchArr(a, n, mobile); // swapping the elements // according to the // direction i.e. dir[]. if (dir[a[pos - 1] - 1] == RIGHT_TO_LEFT) { int temp = a[pos - 1]; a[pos - 1] = a[pos - 2]; a[pos - 2] = temp; } else if (dir[a[pos - 1] - 1] == LEFT_TO_RIGHT) { int temp = a[pos]; a[pos] = a[pos - 1]; a[pos - 1] = temp; } // changing the directions // for elements greater // than largest mobile integer. for ( int i = 0; i < n; i++) { if (a[i] > mobile) { if (dir[a[i] - 1] == LEFT_TO_RIGHT) dir[a[i] - 1] = RIGHT_TO_LEFT; else if (dir[a[i] - 1] == RIGHT_TO_LEFT) dir[a[i] - 1] = LEFT_TO_RIGHT; } } for ( int i = 0; i < n; i++) Console.Write(a[i]); Console.Write( " " ); return 0; } // To end the algorithm // for efficiency it ends // at the factorial of n // because number of // permutations possible // is just n!. public static int fact( int n) { int res = 1; for ( int i = 1; i <= n; i++) res = res * i; return res; } // This function mainly // calls printOnePerm() // one by one to print // all permutations. public static void printPermutation( int n) { // To store current // permutation int [] a = new int [n]; // To store current // directions bool [] dir = new bool [n]; // storing the elements // from 1 to n and // printing first permutation. for ( int i = 0; i < n; i++) { a[i] = i + 1; Console.Write(a[i]); } Console.Write( "\n" ); // initially all directions // are set to RIGHT TO // LEFT i.e. 0. for ( int i = 0; i < n; i++) dir[i] = RIGHT_TO_LEFT; // for generating permutations // in the order. for ( int i = 1; i < fact(n); i++) printOnePerm(a, dir, n); } // Driver function public static void Main() { int n = 4; printPermutation(n); } } // This code is contributed by nitin mittal. |
Javascript
// JavaScript program to print all permutations using // Johnson and Trotter algorithm. const LEFT_TO_RIGHT = true ; const RIGHT_TO_LEFT = false ; // Utility functions for finding the // position of largest mobile integer in a[]. function searchArr(a, n, mobile) { for ( var i = 0; i < n; i++) { if (a[i] === mobile) { return i + 1; } } } // To carry out step 1 of the algorithm i.e. // to find the largest mobile integer. function getMobile(a, dir, n) { var mobile_prev = 0; var mobile = 0; for ( var i = 0; i < n; i++) { // direction 0 represents RIGHT TO LEFT. if (dir[a[i] - 1] === RIGHT_TO_LEFT && i !== 0) { if (a[i] > a[i - 1] && a[i] > mobile_prev) { mobile = a[i]; mobile_prev = mobile; } } // direction 1 represents LEFT TO RIGHT. if (dir[a[i] - 1] === LEFT_TO_RIGHT && i !== n - 1) { if (a[i] > a[i + 1] && a[i] > mobile_prev) { mobile = a[i]; mobile_prev = mobile; } } } if (mobile === 0 && mobile_prev === 0) { return 0; } else { return mobile; } } // Prints a single permutation function printOnePerm(a, dir, n) { var mobile = getMobile(a, dir, n); var pos = searchArr(a, n, mobile); // swapping the elements according to the // direction i.e. dir[]. if (dir[a[pos - 1] - 1] === RIGHT_TO_LEFT) { [a[pos - 1], a[pos - 2]] = [a[pos - 2], a[pos - 1]]; } else if (dir[a[pos - 1] - 1] === LEFT_TO_RIGHT) { [a[pos], a[pos - 1]] = [a[pos - 1], a[pos]]; } // changing the directions for elements // greater than largest mobile integer. for ( var i = 0; i < n; i++) { if (a[i] > mobile) { if (dir[a[i] - 1] === LEFT_TO_RIGHT) { dir[a[i] - 1] = RIGHT_TO_LEFT; } else if (dir[a[i] - 1] === RIGHT_TO_LEFT) { dir[a[i] - 1] = LEFT_TO_RIGHT; } } } console.log(a.join( "" )); } // To end the algorithm for efficiency it ends // at the factorial of n because number of // permutations possible is just n!. function fact(n) { var res = 1; for ( var i = 1; i <= n; i++) { res = res * i; } return res; } // This function mainly calls printOnePerm() // one by one to print all permutations. function printPermutation(n) { // To store current permutation var a = []; // To store current directions var dir = []; // storing the elements from 1 to n and // printing first permutation. for ( var i = 0; i < n; i++) { a[i] = i + 1; } console.log(a.join( "" )); // initially all directions are set // to RIGHT TO LEFT i.e. 0. for ( var i = 0; i < n; i++) { dir[i] = RIGHT_TO_LEFT; } // for generating permutations in the order. for ( var i = 1; i < fact(n); i++) { printOnePerm(a, dir, n); } } // Driver code var n = 4; printPermutation(n); // This Code is Contributed by Prasad Kandekar(prasad264) |
1234 1243 1423 4123 4132 1432 1342 1324 3124 3142 3412 4312 4321 3421 3241 3214 2314 2341 2431 4231 4213 2413 2143 2134
Time Complexity: O(n*n!)
Auxiliary Space: O(n)
Contact Us