PermutationIterator.java

Go to the documentation of this file.

package aud.util;
 
public class PermutationIterator implements java.util.Iterator<int[]> {
 
  private int[] p_  = null; // current permutation
 
  void swap(int i,int j) {
    int t=p_[i]; p_[i]=p_[j]; p_[j]=t;
  }
  void reverse(int i,int j) {
    --j;
    while (i<j)
      swap(i++,j--);
  }
 
  public PermutationIterator(int n) {
    if (n>0) {
      p_=new int[n];
      for (int i=0;i<n;++i)
        p_[i]=i;            // initial
    }
  }
 
  @Override public boolean hasNext() {
    return p_!=null;
  }
 
  @Override public int[] next() {
    int[] p = new int[p_.length];
 
    for (int j=0;j<p_.length;++j)
      p[j]=p_[j];
 
    int last=p_.length;
    int i=last-1;
 
    for (;;) {
      int ii=i;
      if (p_[--i]<p_[ii]) {
        int j=last;
        while (p_[i]>=p_[--j]) {}
        swap(i,j);
        reverse(ii,last);
 
        break;
      }
      else if (i==0) {
        //reverse(0,last);
        p_=null;
        break;
      }
    }
 
    return p;
  }
 
  @Override public void remove() {
    throw new UnsupportedOperationException();
  }
 
  public static void main(String[] args) {
 
    int n=args.length>0 ? Integer.parseInt(args[0]) : 3;
 
    for (PermutationIterator ii=new PermutationIterator(n);ii.hasNext();) {
      int[] p=ii.next();
      for (int j : p)
        System.out.print(j);
      System.out.println();
    }
  }
}