Permutation
by Isai Damier, Android Engineer @ Google

/***************************************************************************
 * Author: Isai Damier
 * Title: Permutation
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Returns a list of all the permutations of the given set
 *
 * Sample Input: {1,2,3}
 * Sample Output: {1,2,3}; {1,3,2}; {2,1,3}; {2,3,1}; {3,1,2}; {3,2,1}
 *
 * Technical Details:
 *   One way of verifying the correctness of the result is to count the
 *   number of permutations returned. From arithmetics, we know that the
 *   number of permutations for a set is equal to the factorial of the size
 *   of the set: 3! = 6.
 *
 *   This recursive algorithm is usually referred to as Heap's permutation,
 *   in honor of B. R. Heap.
 *
 *   If a programmer simply wishes to print the permutations instead of
 *   returning them in a list, [code 2] should replace [code 1] below.
 *
 *   [code 1]:
 *     if(1 == n)
 *       factorials.add(Arrays.copyOf(list, list.length));
 *
 *   [code 2]:
 *    if(1 == n){
 *     for(int i: list)
 *      System.out.print(i+", ");
 *     System.out.println();
 *    }
 *
 **************************************************************************/ 
 public List<Integer[]> permutation(Integer[] list) {
  List<Integer[]> factorials = new ArrayList<Integer[]>();
  permutation(list, list.length, factorials);
  return factorials;
}// permutation(Integer[])

private void permutation(Integer[] list, int n, List<Integer[]> factorials){
  if (1 == n) {
    factorials.add(Arrays.copyOf(list, list.length));
  } else {
    for (int i = 0; i < n; i++) {
      permutation(list, n - 1, factorials);
      if (0 == n % 2) {
        swap(list, 0, n - 1);
      } else {
        swap(list, i, n - 1);
      }
    }// end for
  }// end if
}

private void swap(Integer[] list, int x, int y) {
  Integer t = list[x];
  list[x] = list[y];
  list[y] = t;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class NumbersTest {

  /**
   * Test of permutation method, of class Numbers.
   */
  @Test
  public void testPermutation() {
    System.out.println("permutation");
    Numbers numbers = new Numbers();
    Integer[][] expected =
        {{1, 2, 3}, {2, 1, 3}, {3, 2, 1}, {2, 3, 1}, {3, 1, 2}, {1, 3, 2}};
    List<Integer[]> result = numbers.permutation(new Integer[]{1, 2, 3});

    int e = 0, r = 0;
    while (e < expected.length || r < result.size()) {
      assertTrue(Arrays.equals(expected[e++], (result.get(r++))));
    }
  }
}