Combination Listing

Combination.java

import java.util.ArrayList;
import java.util.List;

public class Combination<T> {
	public static void main(String[] args) throws Exception {
		List<Integer> data = new ArrayList<Integer>();
		for(int i=1; i<=3; i++) {
			data.add(i);
		}
		List<List<Integer>> combination = new Combination<Integer>().makeCombination(data, 2);
		System.out.println(combination);
		// [[1, 2], [1, 3], [2, 3]]
	}

	/**
	 * 与えられたリストと組み合わせの数を元に組み合わせを列挙して返す
	 * @param data データ
	 * @param size 組み合わせの数
	 * @return 組み合わせリスト
	 */
	public List<List<T>> makeCombination(List<T> data, int size) {
		List<List<T>> result = new ArrayList<List<T>>();
		final int dataSize = data.size();
		// 組み合わせの数 = 2^dataSize
		final int loopCount = (int)Math.pow(2, dataSize);

		int[] bits = new int[dataSize];
		for(int i=0; i<loopCount; i++) {
			for(int j=0; j<dataSize; j++) {
				// 桁ごとのビットを計算：(i / 2^j) % 2
				bits[j] = ((int)(i/(int)Math.pow(2, j))) % 2;
			}

			if(size == countBits(bits)) {
				// 指定された組み合わせの数と、ビットカウントが同じものを結果リストに追加する。
				result.add(makeList(data, bits));
			}
		}

		return result;
	}

	/**
	 * 1が立っている数を返す
	 * @param bits ビットリスト
	 * @return
	 */
	private int countBits(int[] bits) {
		int result = 0;
		for(int bit : bits) {
			if(bit == 1) {
				result++;
			}
		}

		return result;
	}

	/**
	 * 1が立っている位置のデータをリストとして返す
	 * @param data リスト
	 * @param bits ビットリスト
	 * @return リスト
	 */
	private List<T> makeList(List<T> data, int[] bits) {
		List<T> result = new ArrayList<T>();
		final int bitsCount = bits.length;

		for(int i=0; i<bitsCount; i++) {
			if(bits[i] == 1) {
				result.add(data.get(i));
			}
		}

		return result;
	}
}