Johnson Trotter Algorithm help

[Hunter McMillen]

**Overview:**

I am trying to implement the Johnson Trotter Algorithm in Java so that I can solve a problem on Project Euler. I have looked and looked but as far as I can see I have everything implemented right, which you know is wrong, otherwise I wouldn't be asking this question


The basic algorithm goes like this:

 Johnson Trotter(n)
    //Input: A positive integer n
    //Output: A list of all permutations(0..n)
    
    initialize the first permutation with: <0, <1, <2
    //(all elements pointing left)
    
    while ( //there exists a mobile element ) 
         //find the largest mobile element K
         //swap K with the element it points toward
         //reverse the direction of all elements > K 
         //add the permutation to a list

I have created an `Element` object that has attributes

(value, isMobile, Direction) 

to use for this algorithm. When I am swapping values, only one swap occurs, then after that the original order is printed over and over.


**Code:**

   public void generatePermutations(int n)
   {
      ArrayList<String> permutations = new ArrayList<String>();
      ArrayList<Element> elements    = new ArrayList<Element>();
   
      //Initialize the first permutation, all Elements are mobile and point LEFT
      for(int i = 0; i < n; i++)
     {
         elements.add(new Element(i, true, Direction.LEFT));
      }
   
   	//add initial permutation to the list 
      permutations.add(combineElementsToString(elements));
		
   
      while(hasMobileElement(elements))
      {
      	//find the largest mobile element
         int maxIndex  = getLargestMobileIndex(elements); 
         Element k     = elements.get(maxIndex);
      
      	//Swap the largest Element with the Element it points to
         if(k.getDirection() == Direction.LEFT)
         {
            //get the index of the element to the left of k
            int leftIndex = (maxIndex - 1) >= 0 ? (maxIndex - 1) : maxIndex;
				
            Collections.swap(elements, maxIndex, leftIndex);
         }
         else
         {
	     //get the index of the element to the right of k
	     int rightIndex = (maxIndex + 1) < elements.size() ? (maxIndex + 1) : maxIndex;
				
            Collections.swap(elements, maxIndex, rightIndex);
         }
      
      	//reverse the direction of all elements larger than K
         for(Element e : elements)
         {
            //System.out.println(e);
            if(e.getValue() > k.getValue())
            {
	        Direction opposite = Direction.opposite(e.getDirection());
               e.setDirection(opposite);
            }
         }
  
      	//add the new permutation to the list
         permutations.add(combineElementsToString(elements));
      }
   }

   public String combineElementsToString(ArrayList<Element> elements)
   {
      String perm = "";
   
      for(Element e : elements)
      {
         perm += Integer.toString(e.getValue());
      }
   
      return perm;
   }

   public int getLargestMobileIndex(ArrayList<Element> elements)
   {
      int maxIndex = 0;
   
      for(int i = 0; i < elements.size(); i++)
      {
         if(elements.get(i).isMobile() && elements.get(i).getValue() > elements.get(maxIndex).getValue())
         {
            maxIndex = i;
         }
      }
   
      return maxIndex;
   }

   public boolean hasMobileElement(ArrayList<Element> elements)
   {
      for(Element e : elements)
      {
         if(e.isMobile()) 
            return true;
      }
   
      return false;
   }

**Expectations:**
I would expect the algorithm to do something like this

Start:

<0 <1 <2
<0 <2 <1
<2 <0 <1

etc

**Actual**

This is what it actually does

Start:

<0 <1 <2
<0 <2 <1
<2 <0 <1
<2 <0 <1

it doesnt change after the second swap

Any help would be awesome, also if you have comments/pointers about my style those would also be much appreciated, Thanks.

Sorry for long post.

PS - Also posted on SO: http://stackoverflow.com/questions/6877504/johnson-trotter-algorithm

[Hunter McMillen]

Someone on SO found my problem, I will post the solution after I have made the necessary changes

Hunter

[Hunter McMillen]

Sorry it has taken so long, this is the solution I came up with using the Johnson Trotter algorithm, if anyone is interested. Any feedback on my code would be appreciated.

Thanks

//enum declaration of Direction of Element objects
      public enum Direction 
      { 
         LEFT, RIGHT;
      
         /**
      	 * Returns the opposite direction of d
      	 */
         public static Direction opposite(Direction d)
         {
            if(d == Direction.LEFT) 
               return Direction.RIGHT;
            else
               return Direction.LEFT;
         }
      }

    //this is inside of Euler24, I removed it here to improve readability
    private class Element 
      {
         private boolean isMobile;
         private int value;
         private Direction direction;
      
         public Element(int value, boolean isMobile, Direction dir)
         {
            this.value     = value;
            this.isMobile  = isMobile;
            this.direction = dir;
         } 
      
         public boolean isMobile()
         {
            return this.isMobile;
         }
      
         public Direction getDirection()
         {
            return this.direction;
         }
      
         public int getValue()
         {
            return this.value;
         }
      
         public void setMobile(boolean in)
         {
            this.isMobile = in;
         }
      
         public void setDirection(Direction in)
         {
            this.direction = in;
         }
      
         public String toString()
         {
            return "Value: " + this.getValue() + "\tMobile?: " 
               + this.isMobile() + "\tDirection: " + this.getDirection();
         }
      }

   import java.util.ArrayList;
   import java.util.Collections;
   import java.util.Arrays;
   import java.util.*;
   import java.io.*;

    //Find Millionith lexographical permutation of the digits 0,9
   public class Euler24
   {
   	
      public Euler24()
      {
      }
   
      public static void main(String[] args)
      {
         Euler24 e = new Euler24();
         e.generatePermutations(10);
      }
   
      /**
       * Generates all permutations from 0 to n
       * Uses the Johnson Trotter algorithm
       */
      public void generatePermutations(int n)
      {
         ArrayList<String> permutations = new ArrayList<String>();
         ArrayList<Element> elements    = new ArrayList<Element>();
      
      	//Start Johnson Trotter
      	//Initialize the first permutation, all Elements are mobile and point LEFT
         for(int i = 0; i < n; i++)
         {
            elements.add(new Element(i, true, Direction.LEFT));
         }
      
      	//add initial permutation to the list 
         permutations.add(combineElementsToString(elements));
  
      
         while(hasMobileElement(elements))
         {
         	//find the largest mobile element
            int maxIndex  = getLargestMobileIndex(elements); 
            Element k     = elements.get(maxIndex);
         
         	//Swap the largest Element with the Element it points to
            if(k.getDirection() == Direction.LEFT)
            {
            	//get the index of the element to the left of k
               int leftIndex = (maxIndex - 1) >= 0 ? (maxIndex - 1) : maxIndex;
            
               Collections.swap(elements, maxIndex, leftIndex);
            }
            else
            {
            	//get the index of the element to the right of k
               int rightIndex = (maxIndex + 1) < elements.size() ? (maxIndex + 1) : maxIndex;
            
               Collections.swap(elements, maxIndex, rightIndex);
            }
         
         	//reverse the direction of all elements larger than K
            for(Element e : elements)
            {
            	//System.out.println(e);
               if(e.getValue() > k.getValue())
               {
                  Direction opposite = Direction.opposite(e.getDirection());
                  e.setDirection(opposite);
               }
            }
         
         	//add the new permutation to the list
            permutations.add(combineElementsToString(elements));
            //print(elements);
         }
			
         Collections.sort(permutations);
         System.out.println(permutations.size());
			System.out.println("perm[999999] " + permutations.get(999999));
			System.out.println("perm[1000000] " + permutations.get(1000000));
      	
      }
   
      public String combineElementsToString(ArrayList<Element> elements)
      {
         String perm = "";
      
         for(Element e : elements)
         {
            perm += Integer.toString(e.getValue());
         }
      
         return perm;
      }
   
      public int getLargestMobileIndex(ArrayList<Element> elements)
      {
      	//get the first element in the list
         Element max = null;
      	      	
         for(int i = 0; i < elements.size(); i++)
         {
            Element current = elements.get(i);
         	
            if(current.isMobile() && max == null)
               max = current;
            else if(current.isMobile() && max.isMobile() && current.getValue() > max.getValue())
               max = current;;
         }
      
         return elements.indexOf(max);
      }
   
      public boolean hasMobileElement(ArrayList<Element> elements)
      {
         updateMobility(elements);
         for(Element e : elements)
         {
            if(e.isMobile()) 
               return true;
         }
      
         return false;
      }
       
      public void updateMobility(ArrayList<Element> elements)
      {
         for(int i = 0; i < elements.size(); i++)
         {
            Element e = elements.get(i);
         
            if(e.getDirection() == Direction.LEFT)
            {
               int leftIndex = i - 1;
            	//if there is an element to the left
               if(leftIndex >= 0)
               {
                  Element left = elements.get(leftIndex);
                  if(e.getValue() > left.getValue())
                     e.setMobile(true);
                  else
                     e.setMobile(false);
               }
               else
               {
                  e.setMobile(false);
               }
            }
            else
            {
               int rightIndex = i + 1;
            	//if there is an element to the left
               if(rightIndex < elements.size())
               {
                  Element right = elements.get(rightIndex);
                  if(e.getValue() > right.getValue())
                     e.setMobile(true);
                  else
                     e.setMobile(false);
               }
               else
               {
                  e.setMobile(false);
               }
            }
         }
      }
       
      public void print(ArrayList<Element> elements)
      {
         for(Element e : elements)
         {
            if(e.getDirection() == Direction.LEFT)
               System.out.print("<" + Integer.toString(e.getValue()) + " ");
            else
               System.out.print(Integer.toString(e.getValue()) + "> ");
         }
         System.out.println();
     }
   }