import java.util.Random;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.ArrayList;

/** A random permutation on the elements [0,N-1].
 *
 * @author Jerod Weinman
 * Grinnell College
 * 19 March 2009
 */
public class RandomPermutation implements Iterable<Integer>
{

  /**
   * Construct a permutation of N=length items. A default seed and
   * random number generator are used.
   *
   * @param length Number of items in permutation
   */
  public RandomPermutation(int length)
  {
    this(length, 42);
  }

  /**
   * Construct a permutation of N=length items using the given seed.
   *
   * @param length Number of items in permutation
   * @param seed Seed for default random number generator
   */
  public RandomPermutation(int length, int seed)
  {
    this(length, new Random(seed));
  }

  /**
   * Construct a permutation of N=length items using the given seed.
   *
   * @param length Number of items in permutation
   * @param rand Random number generator for permutation generation
   */
  public RandomPermutation(int length, Random rand)
  {
    this.length = length;
    this.rand = rand;
    indices = new ArrayList<Integer>(length);
    init();
  }

  /** Initialize object to a random permutation of elements. */
  public void init() 
  {
    /* A list of unused indices. List rather than hash is used because
       ordering is important. */
    LinkedList<Integer> unused = new LinkedList<Integer>();

    /* An array for random numbers */
    int r[] = new int[length];

    /* The i'th location is a random number in [0,N-1-i] */
    for (int i=0 ; i<length ; i++) 
    {
      r[i] = rand.nextInt(length-i);
      unused.add(i);
    }

    /* Remap the indices to the full range by iterating over the
    random indices, constantly adding the item at that index, and then
    deleting it, leaving one less item to index.*/
    for (int i=0 ; i<length ; i++) 
    { 
      indices.add(unused.get(r[i]));
      unused.remove(r[i]); 
    }
  }

  public String toString()
  {
    return indices.toString();
  }

  /* Returns an iterator over the randomly permuted elements */
  public Iterator<Integer> iterator()
  {
    return ((ArrayList<Integer>)indices.clone()).iterator();
  }

  /** Number of symbols, N */
  private int length; 

  /** Random object */
  private Random rand;

  /** Current ordering of indices */
  private ArrayList<Integer> indices;

  ////////////////////////////////////////////////////////////////////////////////
  // MAIN
  public static void main(String[] args)
  {
    RandomPermutation perm = new RandomPermutation(4);
    
    for (Integer item : perm )
      System.out.println(item);
    

  }
}