Permutation Listing

Permutation.java

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

public class Permutation<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>> permutation = new Permutation<Integer>().make(data);
		System.out.println(permutation);
		// [[3, 2, 1], [2, 3, 1], [3, 1, 2], [1, 3, 2], [2, 1, 3], [1, 2, 3]]
	}

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

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

			if(!isDuplicateIndexes(indexes)) {
				// インデックスに重複がない場合、結果リストに追加する。
				result.add(makeList(data, indexes));
			}
		}

		return result;
	}

	/**
	 * インデックスに重複があるかどうか検査する
	 * @param indexes
	 * @return 重複がある場合true、そうでない場合false
	 */
	public boolean isDuplicateIndexes(int[] indexes) {
		int[] result = new int[indexes.length];

		for(int i=0; i<indexes.length; i++) {
			result[indexes[i]] = 1;
		}

		for(int i=0; i<result.length; i++) {
			if(result[i] == 0) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 指定リストと指定インデックスリストからリストを抽出して返す
	 * @param data
	 * @param indexes
	 * @return
	 */
	public List<T> makeList(List<T> data, int[] indexes) {
		List<T> result = new ArrayList<T>();

		for(int i=0; i<indexes.length; i++) {
			result.add(data.get(indexes[i]));
		}

		return result;
	}
}