COMBINATOIRE

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
/**
 * Stores all the combinations of P elements in N elements.
 * This class considers that you have a list of N indexed objects.
 * It stores all combinations of the indexes of P elements in these N elements...
 * 
 * The main point here is that you use indexes...
 * Hence you can calculate the combinations once for all...
 * Example: you calculate the combinations of 3 elements in 5, then you can apply the result to any list of 5 elements, 
 * be it a list of strings, of cards, numbers, with the {@link #getCombination(Object[], int, boolean)} method...
 * @author vctrs
 */
public class Combinations {
	/**
	 * Size of the universe (N)
	 */
	private int iN;
	/**
	 * Size of the combinations (P)
	 */
	private int iP; 
	/**
	 * Stores all the combinations.
	 * NB: a combination is stored as an integer, with each bit corresponding to an index being present or not...
	 * example: int = 25 -> bit = 11001 -> means that the combination includes the elements at index 0,3,4
	 * @see #encodeCombination(int[])
	 * @see #decodeCombination(int)
	 * Hence the N<=31 limitation since an int is coded on 31bits (+1 for sign)
	 * But it divides the memory usage by P compared to a 'basic' way of handling combinations...
	 */
	private Collection<Integer> list = new ArrayList<Integer>();
	/**
	 * @return list of all the indexes combinations of P elements in N elements
	 * @see #list
	 */
	public Collection<Integer> getList() {return list;}		
	/**
	 * Calculates the combinations of P in N
	 * @param P Size of the combinations (P)
	 * @param N Size of the universe (N)
	 * @throws Exception if N>31 or P>N
	 */
	public Combinations(int P, int N) throws Exception{
		System.out.println("Combinations of P="+P+" elements in N="+N+" elements");
		if(N>31)throw new Exception("Too many elements for N (Max=31)");
		if(P>N)throw new Exception("No combination if P>N");
		iN = N;
		iP = P;
		findCombinations(0, new int[iP]);//finds the list of combinations...
	}
	/**
	 * Main algorithm to find the combinations
	 * @param index currently filling this index of the current combination
	 * @param currentCombination temporary object used to store the combination 
	 * NB: basically it uses the same method you instinctively use to find combinations manually...
	 */
	private void findCombinations(int index, int[] currentCombination) {
		if (index>=iP) {//combination has the good size	
			list.add(encodeCombination(currentCombination));
		}else{
			int start=0;
			if (index>0) start=currentCombination[index-1]+1;//start from the latest found index...
			for(int i=start;i<iN;i++) {
				currentCombination[index]=i;
				findCombinations(index+1, currentCombination);
			}
		}
	}	
	/**
	 * @param decodedCombination a list of indexes
	 * @return an int that express the given list as a combination
	 */
	private int encodeCombination(int[] decodedCombination){
		int encodedCombination = 0;
		for(int index:decodedCombination)encodedCombination |=  (1 << index);
		return encodedCombination;
	}
	/**
	 * @param encodedCombination a combination expressed as an int
	 * @return the list of indexes linked to the given combination
	 */
	private int[] decodeCombination(int encodedCombination){
		int[] result = new int[iP];
		int index = 0; 
		for(int i=0;i<iN;i++)
			if((0x1 & (encodedCombination >> i))==1){
				result[index] = i;
				index++;
			}
		return result;
	}
	/**
	 * @param universe a collection of objects (that was used to calculate the combination)
	 * @param selectedCombination a combination that should be applied to the given universe
	 * @param complement return the combination (=false) or everything except the combination (=true)?
	 * @return the combination or everything except the combination
	 * NB: the given universe and the selected combination must be linked 
	 * (typically you calculate the list of combinations by taking the size of the universe)
	 * 
	 * See usage in the main method
	 * 
	 * NB: universe is an array, but it could become a collection, given that this collection ensures the order of its elements...
	 * But basically it is more simple to keep it as an array...
	 */
	public <U> Collection<U> getCombination(U[] universe, int selectedCombination, boolean complement){
		Collection<U> result = new ArrayList<U>(iN);
		int usedCombination = complement?~selectedCombination:selectedCombination;		
		for(int i=0;i<iN;i++)if((0x1 & (usedCombination >> i))==1)result.add(universe[i]);		
		return result;
	}	
	/**
	 * @param encodedCombination
	 * @return the given combination as a list of indexes
	 */	
	private String displayCombination(int encodedCombination){
		return Arrays.toString(decodeCombination(encodedCombination))+"\n";
	}
	/**
	 * @return all the indexes combinations linked to this object
	 */
	public String toString(){
		String result="";
		for(Integer i:list)result+=displayCombination(i);
		return result;
	}
	/**
	 * Testing results:
example#1
Combinations of P=3 elements in N=5 elements
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
example#2
Combinations of P=2 elements in N=5 elements
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

example#3
Combinations of P=1 elements in N=1 elements
[0]

example#4
Combinations of P=2 elements in N=1 elements
No combination if P>N
example#5
Combinations of P=1 elements in N=32 elements
Too many elements for N (Max=31)
	 */
	public static void main(String[] args) {
		try {		
			System.out.println("example#1");
			String[] universe = {"a","b","c","d","e"};
			int N = universe.length;
			int P = 3;//look for all the combinations of 3 elements in the given universe...
			Combinations c = new Combinations(P,N);
			for(int combination:c.getList()){
				String sCombination = "";
				Collection<String> cCombination = c.getCombination(universe, combination, false);//returns the list of elements of the original list that are in the given combination...
				for(String s:cCombination)sCombination+=s;//display the combination we just found...
				System.out.println(sCombination);
			}	
			System.out.println("example#2");
			System.out.println(new Combinations(2,5).toString());
			System.out.println("example#3");
			System.out.println(new Combinations(1,1).toString());			
		} catch (Exception e) {
			System.out.println(e.getMessage());
		}
		try {
			System.out.println("example#4");
			System.out.println(new Combinations(2,1).toString());
		} catch (Exception e) {
			System.out.println(e.getMessage());
		}
		try {
			System.out.println("example#5");
			System.out.println(new Combinations(1,32).toString());
		} catch (Exception e) {
			System.out.println(e.getMessage());
		}
	}
}//end of class





/*
 * This file was inspired by the source code of Steven J. Metsker, found at the following address
 * http://www.google.com/codesearch?hl=fr&q=+.java+combination+show:g0x3L0qd_pk:lF718ZCqeDg:_dTa6NgGRHQ&sa=N&cd=41&ct=rc&cs_p=http://www.oozinoz.com/bpwj.zip&cs_f=bpwj/code/sjm/combinatorics/Combinations.java
 * Copyright of the original file: 
 * Copyright (c) 2000 Steven J. Metsker. All Rights Reserved.
 * Steve Metsker makes no representations or warranties about
 * the fitness of this software for any particular purpose,
 * including the implied warranty of merchantability.
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
/**
 * This class provides an iteration of all combinations of P in N objects. 
 */
public class CombinationsTucker<O> implements Iterable<Collection<O>> {
	/**
	 * Stores the universe in a collection with access by index
	 */
	protected ArrayList<O> universeWithArray;
	/**
	 * size of the universe
	 */
	protected int n;
	/**
	 * size of the combinations
	 */
	protected int p;
	/**
	 * Array that keeps track of the next combination to return. 
	 * For example, an index on 5 things taken 3 at a time might contain {0 3 4}. 
	 * This index will be followed by {1 2 3}. 
	 * Initially, the index is {0 ... m - 1}.
	 */
	protected int[] combinationIndex;	
	/**
	 * Create a Combination to iterate through all combinations of the supplied collection, selecting P at a time.
	 *
	 * @param universe the group to choose from
	 * @param p the number to select in each choice
	 * @exception Exception if m is greater than the length of universe, or less than 0.
	 */
	public CombinationsTucker(Collection<O> universe, int p)throws Exception{
		this.n = universe.size();
		this.p = p;
		System.out.println("Combinations of P="+p+" elements in N="+n+" elements");
		if(p>n)throw new Exception("No combinations if P>N");
		if(p<0)throw new Exception("No combinations if P<0");
		this.universeWithArray = new ArrayList<O>(this.n);
		this.universeWithArray.addAll(universe);
		//Find first combination
		combinationIndex = new int[p];
		for(int i=0; i<p; i++) combinationIndex[i]=i;			
	}
	/**
	 * Create a Combination to iterate through all combinations of the supplied collection, selecting P at a time.
	 *
	 * @param universe the group to choose from
	 * @param p the number to select in each choice
	 * @exception Exception if m is greater than the length of universe, or less than 0.
	 */
	public CombinationsTucker(O[] universe, int p)throws Exception{
		this(Arrays.asList(universe),p);
	}	
	/** 
	 * Return an iterator for the combinations. 
	 * */
	public Iterator<Collection<O>> iterator() {
		return new CombinationIterator();
	}
	/**
	 * internal class that calculates the iteration of combinations...
	 * a combination is a collection of P objects(<O>)
	 */
	protected class CombinationIterator implements Iterator<Collection<O>>{
		/**
		 * stores next element existence
		 */
		private boolean next = true;
		/**
		 * @return true, unless we have already returned the last combination.
		 */
		public boolean hasNext() {
			return next;
		}
		/**
		 * Calculates the indexes of the univers'elements that will be in the next combination...
		 * 
		 * Move the index forward a notch. 
		 * The algorithm finds the rightmost index element that can be incremented, increments it, 
		 * and then changes the elements to the right to each be 1 plus the element on their left.
		 * For example, if an index of 5 things taken 3 at a time is at {0 3 4}, 
		 * only the 0 can be incremented without running out of room. 
		 * The next index is {1, 1+1, 1+2) or {1, 2, 3}.
		 * This will be followed by {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}.
		 * The algorithm is from "Applied Combinatorics", by Alan Tucker.
		 */
		private void calculateNextCombination() {
			int i = rightmostCombinationIndexBelowMax();
			if (i >= 0) {
				combinationIndex[i] = combinationIndex[i] + 1;
				for (int j=i+1; j<p; j++) combinationIndex[j] = combinationIndex[j-1] + 1;
			}else{
				next = false;
			}
		}
		/**
		 * keep implementation correct
		 */
		public void remove() {
			throw new UnsupportedOperationException();
		}
		/**
		 * @return the next combination
		 */
		public Collection<O> next() {
			if (!next) return null;
			ArrayList<O> out = new ArrayList<O>(p);
			for(int i=0; i<p; i++) out.add(i, universeWithArray.get(combinationIndex[i]));
			calculateNextCombination();
			return out;
		}
		/**
		 * @return the index which can be bumped up.
		 */
		private int rightmostCombinationIndexBelowMax() {
			int d = n-p;
			for(int i=p-1; i>=0; i--) if(combinationIndex[i]<d+i) return i;
			return -1;
		}
	}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/**
	 * Result of main:
example#1
Combinations of P=2 elements in N=4 elements
ab
ac
ad
bc
bd
cd
end of example#1
example#2
Combinations of P=3 elements in N=5 elements
Alfred	Ben		Carl	
Alfred	Ben		Drew	
Alfred	Ben		Edwin	
Alfred	Carl	Drew	
Alfred	Carl	Edwin	
Alfred	Drew	Edwin	
Ben		Carl	Drew	
Ben		Carl	Edwin	
Ben		Drew	Edwin	
Carl	Drew	Edwin	
end of example#2
	 */
	public static void main(String[] args) {
		try {		
			System.out.println("example#1");
			Collection<String> universe1 = new ArrayList<String>();
			universe1.add("a");
			universe1.add("b");
			universe1.add("c");
			universe1.add("d");
			int P1 = 2;
			CombinationsTucker<String> c1 = new CombinationsTucker<String>(universe1, P1);
			for(Collection<String> combination:c1){
				for(String o:combination)System.out.print(o);
				System.out.println();	
			}
			System.out.println("end of example#1");

			System.out.println("example#2");
			String[] universe2 = {"Alfred", "Ben", "Carl", "Drew", "Edwin"};
			int P2 = 3;
			CombinationsTucker<String> c2 = new CombinationsTucker<String>(universe2, P2);
			for(Collection<String> combination:c2){
				for(String o:combination)System.out.print(o+"\t");
				System.out.println();		
			}
			System.out.println("end of example#2");

		} catch (Exception e) {
			System.out.println(e.getMessage());
		}
	}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
}//end of class