combinatorics.java

传教士与野人过河

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * Provides a static method to generate combinations of items taken r at a time.
 */
class Combinatorics {
	public static Collection combinations(Collection items, int r) {
		if (r == 0) // Return [ [ ] ]. Note that [ ] denotes a List.
			return Collections.nCopies(1, new ArrayList());

		List copy = new ArrayList(items), // To enable subListing of items.
		result = new ArrayList();
		for (int i = 0; i < copy.size(); ++i) {
			Collection subCombs = combinations(
					copy.subList(i + 1, copy.size()), r - 1);
			for (Iterator iter = subCombs.iterator(); iter.hasNext();) {
				// Assign [ [ items.get( i ) ] ] to subComb.
				List subComb = new ArrayList(copy.subList(i, i + 1));

				subComb.addAll((List) iter.next());
				result.add(subComb);
			}
		}
		return result;
	}
}