The Java Program: Permute.java

  1 // Permute.java -- A class generating all permutations
  2 
  3 import java.util.Iterator;
  4 import java.util.NoSuchElementException;
  5 import java.lang.reflect.Array;
  6 
  7 public class Permute implements Iterator {
  8 
  9    private final int size;
 10    private final Object [] elements;  // copy of original 0 .. size-1
 11    private final Object ar;           // array for output,  0 .. size-1
 12    private final int [] permutation;  // perm of nums 1..size, perm[0]=0
 13 
 14    private boolean next = true;
 15 
 16    // int[], double[] array won't work :-(
 17    public Permute (Object [] e) {
 18       size = e.length;
 19       elements = new Object [size];    // not suitable for primitives
 20       System.arraycopy (e, 0, elements, 0, size);
 21       ar = Array.newInstance (e.getClass().getComponentType(), size);
 22       System.arraycopy (e, 0, ar, 0, size);
 23       permutation = new int [size+1];
 24       for (int i=0; i<size+1; i++) {
 25          permutation [i]=i;
 26       }
 27    }
 28       
 29    private void formNextPermutation () {
 30       for (int i=0; i<size; i++) {
 31          // i+1 because perm[0] always = 0
 32          // perm[]-1 because the numbers 1..size are being permuted
 33          Array.set (ar, i, elements[permutation[i+1]-1]);
 34       }
 35    }
 36 
 37    public boolean hasNext() {
 38       return next;
 39    }
 40 
 41    public void remove() throws UnsupportedOperationException {
 42       throw new UnsupportedOperationException();
 43    }
 44 
 45    private void swap (final int i, final int j) {
 46       final int x = permutation[i];
 47       permutation[i] = permutation [j];
 48       permutation[j] = x;
 49    }
 50 
 51    // does not throw NoSuchElement; it wraps around!
 52    public Object next() throws NoSuchElementException {
 53 
 54       formNextPermutation ();  // copy original elements
 55 
 56       int i = size-1;
 57       while (permutation[i]>permutation[i+1]) i--;
 58 
 59       if (i==0) {
 60          next = false;
 61          for (int j=0; j<size+1; j++) {
 62             permutation [j]=j;
 63          }
 64          return ar;
 65       }
 66 
 67       int j = size;
 68       
 69       while (permutation[i]>permutation[j]) j--;
 70       swap (i,j);
 71       int r = size;
 72       int s = i+1;
 73       while (r>s) { swap(r,s); r--; s++; }
 74 
 75       return ar;
 76    }
 77 
 78    public String toString () {
 79       final int n = Array.getLength(ar);
 80       final StringBuffer sb = new StringBuffer ("[");
 81       for (int j=0; j<n; j++) {
 82          sb.append (Array.get(ar,j).toString());
 83          if (j<n-1) sb.append (",");
 84       }
 85       sb.append("]");
 86       return new String (sb);
 87    }
 88 
 89    public static void main (String [] args) {
 90       for (Iterator i = new Permute(args); i.hasNext(); ) {
 91          final String [] a = (String []) i.next();
 92          System.out.println (i);
 93       }
 94    }
 95 }