Permutations.java

package com.meetup.base.util;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class  Permutations<T> implements Iterator<List<T>> {
	private ArrayList<T> _source;
	private int[] _state;
	private int _take;
	private int _index;
	private long _left;

	public Permutations(List<T> src) {
		this(src, src.size());
	}

	public Permutations(List<T> src, int size) {
		_source = new ArrayList<T>(src);
		_left = numPermutations(src.size(), size);

		// probably a way to better optimize space...
		_state = new int[src.size()];
		for(int i = 0; i < _state.length; i++) {
			_state[i] = i;
		}

		_take = size;
		_index = 1;
	}

	// n! / (n - k)!
	private static long numPermutations(int N, int K) {
		long v = 1;
		long M = N - K;
    while (N > M) {
			v *= N--;
		}
		return v;
	}

	public boolean hasNext() {
		return _left > 0;
	}

	public List<T> next() {
		if (_source == null || _left == 0) {
			throw new NoSuchElementException();
		}

		List<T> res = new ArrayList<T>();

		int size = _source.size();
		if (size > 1) {
			if (_index < size - 1) {
				_index++;
			}
			else {
				_index = 1;
			}

			// swap 0 with _index;
			_state[0] ^= _state[_index];
			_state[_index] ^= _state[0];
			_state[0] ^= _state[_index];
		}



		// copy into the returned result
		System.out.print("  state: ");
		for (int i = 0; i < _take; i++) {
			System.out.print("" + _state[i] + ", ");
			res.add(_source.get(_state[i]));
		}
		System.out.println("" + _left + " left.");
		--_left;
		return res;
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}
}