/* Tyler Prete
 * 04/06/2008
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;


public class SubSequence {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LinkedList<Integer> li = new LinkedList<Integer>();
		//ArrayList<Integer> li = new ArrayList<Integer>();
		int count = 30000;
		int subsequenceSize = 1;
		int runtimes = 1;
		for(int i = 1; i <= count; i++) {
			li.add(i);
		}
		long startTime = System.currentTimeMillis();
		List<List<Integer>> results = null;
		for(int i = 0; i < runtimes; i++) {
			results = subn(subsequenceSize, li);
		}
		long totalTime = System.currentTimeMillis() - startTime;
		//print(results);
		System.out.println("Recursive version count: " + results.size());
		System.out.println("Recursive version time: " + totalTime);
		startTime = System.currentTimeMillis();
		results = null;
		for(int i = 0; i < runtimes; i++) {
			results = mysubn(subsequenceSize, li);
		}
		totalTime = System.currentTimeMillis() - startTime;
		//print(results);
		System.out.println("Iterative version count: " + results.size());
		System.out.println("Iterative version time: " + totalTime);

	}
	
	// My iterative solution
	private static <T> List<List<T>> mysubn(int n, List<T> li) {
		List<List<T>> ret = new ArrayList<List<T>>();
		int size = li.size();
		if (n == 0) {
			ret.add(new ArrayList<T>());
			return ret;
		}
		if (li.isEmpty()) {
			return ret;
		}
		if (size < n) {
			return ret;
		}
		if (size == n) {
			ret.add(li);
			return ret;
		}
		
		/* I use counters to actually keep track of where I am in the list,
		 * but iterators to actually get the elements.  This is because we can't
		 * assume what type of list we are accessing.  list.get(n) is O(1) for
		 * ArrayList, but O(n) for LinkedList, so we'd like to minimize these
		 * as much as possible.
		 * The reason we need to keep the counters and ending array, 
		 * instead of going until the iterators run out of elements, 
		 * is we only want them to the point where they could still make a
		 * subsequence.
		 */
		ArrayList<ListIterator<T>> iters = new ArrayList<ListIterator<T>>(n);
		ArrayList<T> currElems = new ArrayList<T>(n);
		int[] counters = new int[n];
		int[] endings = new int[n];
		// Set up our initial values
		for(int i = 0; i < n; i++) {
			iters.add(li.listIterator(i));
			currElems.add(iters.get(i).next());
			counters[i] = i;
			endings[i] = size - n + i;
		}
		// Go until the we don't have enough elements left to make a subsequence
		while(counters[0] <= endings[0]) {
			List<T> sub = new ArrayList<T>();
			for(int i = 0; i < n; i++) {
				sub.add(currElems.get(i));
			}
			ret.add(sub);
			int c = n - 1;
			// Here we figure out how many of the counters (indexes) need updating.
			while(c > 0) {
				if(counters[c] < endings[c])
					break;
				else
					c--;
			}
			// Update the left-most counter (index)
			counters[c]++;
			if(iters.get(c).hasNext())
				currElems.set(c, iters.get(c).next());
			c++;
			// Starting from the next left-most counter (if there is one),
			// set counter to be 1 more than previous counter, and reset
			// the iterator to start there as well.
			while(c < n) {
				// Reset the counter, and reset the iterator
				// to the new starting position.
				counters[c] = counters[c-1] + 1;
				iters.set(c, li.listIterator(counters[c]));
				// We make sure the iterator has another element.
				// The only time this will return false is when we are completely done
				// and the outer while is over.
				if(iters.get(c).hasNext())
					currElems.set(c, iters.get(c).next());
				c++;
			}
		}
		return ret;
	}
	
	// Ray Myers recursive solution
	private static <T> List<List<T>> subn(int n, List<T> li) {
		List<List<T>> ret = new ArrayList<List<T>>();
		if (n == 0) {
			ret.add(new ArrayList<T>());
			return ret;
		}
		if (li.isEmpty()) {
			return ret;
		}
		T x = li.get(0);
		List<T> xs = li.subList(1, li.size());
		for (List<T> sub : subn(n - 1, xs)) {
			sub.add(0, x);
			ret.add(sub);
		}
		ret.addAll(subn(n, xs));
		return ret;
	}
	
	private static <T> void print(List<List<T>> li) {
		for(List<T> l : li) {
			for(T t : l) {
				System.out.print(t + " ");
			}
			System.out.println();
		}
	}

}