/* Author: Denise Roßberg Date: 16.02.2019 Program: Steinhaus-Johnson-Trotter-Algorithm Update:rework getMobile() Suggestions by Bennett Post Input a String --> get all permutations. How the algorithm works: Every number get a direction (start: left). Find the largest mobile number --> a mobile number is a number which is larger than the number in the direction it is looking at. If the mobile number is not the highest number --> all numbers > mobile number change their direction. Swap the largest mobile number with its neighbor to which its direction points. Repeat it until there is no mobile number left in the sequence. Example: 123 <1 <2 <3 largest mobile(m) = 3 <1 <3 <2 m = 3 <3 <1 <2 m = 2, change direction of 3 3> <2 <1 m = 3 <2 3> <1 m = 3 <2 <1 3> no mobile number left Output: 123 132 312 321 231 213 Example: 1234 <1 <2 <3 <4 m = 4 <1 <2 <4 <3 m = 4 <1 <4 <2 <3 m = 4 <4 <1 <2 <3 m = 3, switch 4 4> <1 <3 <2 m = 4 <1 4> <3 <2 m = 4 <1 <3 4> <2 m = 4 <1 <3 <2 4> m = 3, switch 4 <3 <1 <2 <4 m = 4 <3 <1 <4 <2 m = 4 <3 <4 <1 <2 m = 4 <4 <3 <1 <2 m = 2, switch 3,4 4> 3> <2 <1 m = 4 3> 4> <2 <1 m = 4 3> <2 4> <1 m = 4 3> <2 <1 4> m = 3, switch 4 <2 3> <1 <4 m = 4 <2 3> <4 <1 m = 4 <2 <4 3> <1 m = 4 <4 <2 3> <1 m = 3, switch 4 4> <2 <1 3> m = 4 <2 4> <1 3> m = 4 <2 <1 4> 3> m = 4 <2 <1 3> 4> no mobile number left 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 */ import java.util.HashMap; public class Permutation{ private int[] index; private String input; private HashMap direction; public Permutation(String input){ this.input = input; index = new int[input.length()]; direction = new HashMap<>(); } public void createPermutation(){ //at the beginning all numbers (index of items) are pointing from right to left //<0 <1 <2 ... for(int i = 0; i < index.length; i++){ index[i] = i; direction.put(i, "left"); } int mobile = 0; while(mobile != -1){ mobile = getMobile(); printPermutation(); swap(mobile); } } public int getMobile(){ //find largest mobile number (by Bennett Post) //return -1 if no number is found int lm1 = index.length - 1; int maxMobile = -1; // slicing loop to avoid "array index test" if(direction.get(index[0]) == "right"){ if(index[0] > index[1]){ maxMobile = index[0]; } } for(int i = 1; i < lm1; i++){ if(index[i] > maxMobile){ if(direction.get(index[i]) == "left"){ if(index[i] > index[i-1]) { maxMobile = index[i]; } }else{ if(index[i] > index[i + 1]) { maxMobile = index[i]; } } } } if(direction.get(lm1) == "left"){ if(index[lm1] > maxMobile && index[lm1] > index[lm1-1]){ maxMobile = index[lm1]; } } //change direction of numbers > maxMobile for(int i = 0; i < index.length; i++){ if(maxMobile < index[i]){ if(direction.get(index[i]) == "left"){ direction.put(index[i],"right"); }else{ direction.put(index[i],"left"); } } } return maxMobile; } public void swap(int mobile){ //get index of mobile int x = 0; for(int i = 0; i < index.length; i++){ if(mobile == index[i]){ x = i; } } //position of mobile = index[x] //left: index[x] <> index[x-1] //right: index[x] <> index[x+1] if(direction.get(mobile) == "left"){ int temp = index[x]; index[x] = index[x-1]; index[x-1] = temp; }else{ int temp = index[x]; index[x] = index[x+1]; index[x+1] = temp; } } //print every char from input //--> input.charAt(index[i]) public void printPermutation(){ for(int i = 0; i < index.length; i++){ System.out.print(input.charAt(index[i])); } System.out.println(); } } import java.util.Scanner; public class Program { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String input = scan.nextLine(); Permutation perm = new Permutation(input); perm.createPermutation(); } }

steinhaus-johnson-trotter-algorithm