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

  public Permutation(String str) {
    for(int x=0;x<str.length();x++) {
      DirectionalEntity entity = new DirectionalEntity(String.valueOf(str.charAt(x)), -1);
      entityList.add(entity);
    }

    Collections.sort(entityList);
    sortedList.addAll(entityList);
    Collections.reverse(sortedList);

    //1st Permutation: SortedList
    for(DirectionalEntity e : entityList) {
      System.out.print(e.getEntity()+" ");
    }
    System.out.println("");
    numPermutations = numPermutations.add(BigInteger.ONE);
  }

  public void  getPermutation() {
    while(true) {
      DirectionalEntity mobileDirectionalEntity = getMaxMobileDirectionalEntity();
      if(mobileDirectionalEntity == null) {
        // all permutations have been found
        System.out.println("Total permutations: "+numPermutations);
        break;
      }
      if(mobileDirectionalEntity.getDir() == 1) {
        // Swap this with the right element in the list
        int positionInOriginalList = entityList.indexOf(mobileDirectionalEntity);
        entityList.set(positionInOriginalList, entityList.get(positionInOriginalList+1));
        entityList.set(positionInOriginalList+1, mobileDirectionalEntity);
      }
      else {
        // Swap this with the left element in the list
        int positionInOriginalList = entityList.indexOf(mobileDirectionalEntity);
        entityList.set(positionInOriginalList, entityList.get(positionInOriginalList-1));
        entityList.set(positionInOriginalList-1, mobileDirectionalEntity);
      }

      // We have got a unique permutation - print this
      for(DirectionalEntity e : entityList) {
        System.out.print(e.getEntity()+" ");
      }

      System.out.println("");
      numPermutations = numPermutations.add(BigInteger.ONE);

      // Now reverse the direction of all the numbers greater than mobileDirectionalNumber
      for(DirectionalEntity e : entityList) {
        if(mobileDirectionalEntity.compareTo(e) &lt; 0)
        e.reverseDir();
      }
    }
  }

  /**
  * Gets the maximum mobile directional number by checking
  * the numbers in decreasing order of magnitude
  * @return max mobileDirectionalNumber, if it is exist, else null
  */
  private DirectionalEntity getMaxMobileDirectionalEntity() {
    for(DirectionalEntity dirEntity : sortedList) {
      DirectionalEntity maxDirEntity = dirEntity;
      // Now check for the position of maxDirNum in original List
      // to see if this maxDirNum is actually a mobile directional number
      int positionInOriginalList = entityList.indexOf(maxDirEntity);
      if((maxDirEntity.getDir() == -1 && (positionInOriginalList != 0 &&
        entityList.get(positionInOriginalList-1).compareTo(maxDirEntity) < 0)
        || (maxDirEntity.getDir() == 1 && (positionInOriginalList != entityList.size()-1 && entityList.get(positionInOriginalList+1).compareTo(maxDirEntity) < 0)))) {
      // This is the max mobile directional number - return this
        return maxDirEntity;
      }
    }
    return null; // No more mobile directional numbers exist. All the permutations have been found.
   }
}

Complete source code can be downloaded from here
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