B. Heap's permutation algorithm

HeapPermute.java

import java.util.Arrays;

/**
 * http://lucitworks.com/Snippets/Algorithms/permutation.htm
 */
public class HeapPermute {

	private static void swap(int[] v, int i, int j) {
		int t = v[i]; v[i] = v[j]; v[j] = t;
	}

	public void permute(int[] v, int n) {
		if (n == 1) {
			System.out.println(Arrays.toString(v));
		} else {
			for (int i = 0; i < n; i++) {
				permute(v, n-1);
				if (n % 2 == 1) {
					swap(v, 0, n-1);
				} else {
					swap(v, i, n-1);
				}
			}
		}
	}

	public static void main(String[] args) {
		int[] ns = {1, 2, 3, 4};
		new HeapPermute().permute(ns, ns.length);
	}

}

Sweet! Arigatou Gozaimasu, Ishikawa-San! 😄

This isn't quite Heap's permutation algorithm because it does too many swaps. There are 24 permutations of an array with four elements and Heap's algorithm should do 23 swaps, but this implementation does 40 swaps. The Wikipedia version is currently better in that respect.

The difference is that on the n-1 pass through the inner loop, this implementation swaps after the return from the recursive permute() call. On even length cases, this leads to swaps like swap(v, n-1, n-1) which is unnecessary, but there are unnecessary swaps for odd length cases, too.

It doesn't appear to affect the correctness of the output, though-- I tested on arrays up to length 8.