Java code for Permutation using Steinhaus–Johnson–Trotter algorithm

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 entityList = new ArrayList();
private BigInteger numPermutations = new BigInteger(“0″);
private ArrayList sortedList = new ArrayList();

public Permutation(String str) {
for(int x=0;xhere
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.


Related Posts

Share

Filed Under: AlgorithmsCodesJavaOpen Source

Tags:

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

RSSComments (0)

Trackback URL

Leave a Reply

*

AWSOM Powered