# Java code for Permutation using Steinhaus–Johnson–Trotter algorithm

Saurabh | Jan 11, 2014 | Comments 0

Steinhaus–Johnson–Trotter algorithm is an efficient algorithm to find the permutations of a set of entities.

The code given here use Even’s speedup to improve the running time of the algorithm by storing additional information for each element in the permutation: its position, and a direction (positive or negative) in which it is currently moving.

The class DirectionalEntity has the entity which is to be sorted, and the direction associated to that entity:

private String entity; private int dir; // can be -1 or 1 depending on the dir in which entity is moving public DirectionalEntity(String entity, int dir) { this.entity = entity; this.dir = dir; }

So, if an entity has direction +1, it means it is looking towards right, else if it has direction -1, it means it is looking towards left. Now a DirectionalEntity is said to be ** mobile** if it is greater than its immediate neighbor in the direction it is looking at.

The complete DirectionalEntity Class can be something like:

public class DirectionalEntity implements Comparable<DirectionalEntity> { private String entity; private int dir; // can be -1 or 1 depending on the position public DirectionalEntity(String entity, int dir) { this.entity = entity; this.dir = dir; } public DirectionalEntity() { // TODO Auto-generated constructor stub } @Override public int compareTo(DirectionalEntity directionalEntity) { return (this.entity.compareTo(directionalEntity.entity)); } public void reverseDir() { this.dir = dir * (-1); } public String getEntity() { return entity; } public int getDir() { return dir; } }

The Johnson-Trotter algorithm can now be described in five lines:

```
1. Initialize the first permutation with <e1 <e2 ... <en
while there exists a mobile integer
2. find the largest mobile integer k
3. swap k and the adjacent integer it is looking at
4. reverse the direction of all integers larger than k
```

The class Permutation therefore, will have 2 important methods:

1)

getMaxMobileDirectionalEntity()

which will return the largest mobile entity from the list.

2)

getPermutation()

which will perform steps 3 and 4 of the above mentioned algorithm.

So, the Permutation class will look something like:

public class Permutation {

private List

private BigInteger numPermutations = new BigInteger(“0”);

private ArrayList

public Permutation(String str) {

for(int x=0;x

In this project, any string can be given as input – eg: abcd, 1234, ab32, ab*$, abb332 – all are valid inputs and correct permutations will be generated.

**Filed Under**: Algorithms • Codes • Java • Open Source

**About the Author**: Software Engineer - Advanced Search & Recommendation at Rovi