|
public class TestGetCombination {
public static void main(String[] args) {
TestGetCombination testGetCombination = new TestGetCombination();
testGetCombination.start();
}
public void start() {
// 인덱스 4개 중 3개 선택하기 예제
// ex) 0, 1, 2, 3, 4
int totalCount = 4;
int countToGet = 3;
ArrayList<ArrayList<Integer>> resultList = null;
// 조합 구하기
System.out.println(totalCount + “개 중 ” + countToGet + “개 조합 경우의 수 구하기”);
resultList = getCombination(totalCount, countToGet);
if (resultList != null && resultList.size() > 0) {
int count = resultList.size();
System.out.println(“count : ” + count);
for (int i=0; i<count; i++) {
System.out.println(i + ” : ” + resultList.get(i));
}
}
System.out.println();
// 순열 구하기
System.out.println(totalCount + “개 중 ” + countToGet + “개 순열 경우의 수 구하기”);
resultList = getPermutation(totalCount, countToGet);
if (resultList != null && resultList.size() > 0) {
int count = resultList.size();
System.out.println(“count : ” + count);
for (int i=0; i<count; i++) {
System.out.println(i + ” : ” + resultList.get(i));
}
}
}
/**
* 조합 구하기
*
* ex 1) totalCount == 4
* countToGet == 1
* resultList == [[0],
* [1],
* [2],
* [3]]
*
* ex 2) totalCount == 4
* countToGet == 2
* resultList == [[0, 1],
* [0, 2],
* [0, 3],
* [1, 2],
* [1, 3],
* [2, 3]]
*
* ex 3) totalCount == 4
* countToGet == 3
* resultList == [[0, 1, 2],
* [0, 1, 3],
* [0, 2, 3],
* [1, 2, 3]]
*
*
*
* @param totalCount
* @param countToGet
* @return
*/
public ArrayList<ArrayList<Integer>> getCombination(int totalCount, int countToGet) {
ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();
getCombinationCore(resultList, null, 0, totalCount, countToGet);
return resultList;
}
/**
* 조합 구하기 재귀메서드
* 넘겨받은 resultList 객체에 경우의 수를 담는다. resultList 가 사실상의 리턴값이다.
*
* @param resultList
* @param inputResult
* @param axisIndex
* @param totalCount
* @param countToGet
*/
private void getCombinationCore(ArrayList<ArrayList<Integer>> resultList, ArrayList<Integer> inputResult, int axisIndex, int totalCount, int countToGet) {
for (int i=axisIndex; i<totalCount; i++) {
ArrayList<Integer> oneResult = null;
if (axisIndex == 0) {
oneResult = new ArrayList<Integer>();
} else {
oneResult = (ArrayList<Integer>) inputResult.clone();
}
// 1개씩 인덱스를 담는다.
oneResult.add(i);
if (oneResult.size() == countToGet) {
// countToGet 개 만큼 담았으면 resultList 객체에 추가한다.
resultList.add(oneResult);
} else if (oneResult.size() < countToGet) {
// countToGet 개 만큼 담을 때까지 재귀한다.
getCombinationCore(resultList, oneResult, i + 1, totalCount, countToGet);
} else {
break;
}
}
}
/**
* 순열 구하기
*
* ex 1) totalCount == 4
* countToGet == 1
* resultList == [[0],
* [1],
* [2],
* [3]]
*
* ex 2) totalCount == 4
* countToGet == 2
* resultList == [[0, 1], [1, 0],
* [0, 2], [2, 0],
* [0, 3], [3, 0],
* [1, 2], [2, 1],
* [1, 3], [3, 1],
* [2, 3], [3, 2]]
*
* ex 3) totalCount == 4
* countToGet == 3
* resultList == [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0],
* [0, 1, 3], [0, 3, 1], [1, 0, 3], [1, 3, 0], [3, 0, 1], [3, 1, 0],
* [0, 2, 3], [0, 3, 2], [2, 0, 3], [2, 3, 0], [3, 0, 2], [3, 2, 0],
* [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
*
* @param totalCount
* @param countToGet
* @return
*/
public ArrayList<ArrayList<Integer>> getPermutation(int totalCount, int countToGet) {
// 1. 조합 구하기
ArrayList<ArrayList<Integer>> combinationList = getCombination(totalCount, countToGet);
if (combinationList == null || combinationList.size() == 0) {
return null;
}
// 2. 모든 조합에 대해 순열 구하기. 다시 말해, 각 조합에 대해 순서 바꾸기.
ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();
int count = combinationList.size();
for (int i=0; i<count; i++) {
// 특정 조합에 대해 순열 구하기
getPermutationCore(resultList, combinationList.get(i));
}
return resultList;
}
/**
* 특정 조합에 대해 순열 구하기. 다시 말해, 각 조합에 대해 순서 바꾸기.
* 넘겨받은 resultList 객체에 경우의 수를 담는다. resultList 가 사실상의 리턴값이다.
*
* ex 1) inputList == [0]
* resultList 객체에 [[0]] 추가
*
* ex 2) inputList == [0, 1]
* resultList 객체에 [[0, 1], [1, 0]] 추가
*
* ex 3) inputList == [0, 1, 2]
* resultList 객체에 [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]] 추가
*
* ex 4) inputList == [1, 2, 3]
* resultList 객체에 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 추가
*
* @param resultList
* @param inputList
*/
private void getPermutationCore(ArrayList<ArrayList<Integer>> resultList, ArrayList<Integer> inputList) {
// 인덱스리스트 구하기
ArrayList<ArrayList<Integer>> suffledIndexList = getSuffledIndexList(inputList.size());
if (suffledIndexList == null || suffledIndexList.size() == 0) {
return;
}
int count = suffledIndexList.size();
for (int i=0; i<count; i++) {
ArrayList<Integer> oneResult = new ArrayList<Integer>();
ArrayList<Integer> indexList = suffledIndexList.get(i);
for (int j=0; j<indexList.size(); j++) {
oneResult.add(inputList.get(indexList.get(j)));
}
resultList.add(oneResult);
}
}
/**
* 인덱스리스트 구하기
*
* ex 1) totalCount == 1 일 경우, [[0]] 리턴
* ex 2) totalCount == 2 일 경우, [[0, 1], [1, 0]] 리턴
* ex 3) totalCount == 3 일 경우, [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]] 리턴
*
* @param count
* @return
*/
private ArrayList<ArrayList<Integer>> getSuffledIndexList(int count) {
ArrayList<ArrayList<Integer>> suffledIndexList = new ArrayList<ArrayList<Integer>>();
shuffleRecursively(suffledIndexList, null, count, null);
return suffledIndexList;
}
/**
* 인덱스리스트 구하기 재귀메서드
* 넘겨받은 resultList 객체에 경우의 수를 담는다. resultList 가 사실상의 리턴값이다.
*
* @param resultList
* @param inputResult
* @param totalCount
* @param exceptList
*/
private void shuffleRecursively(ArrayList<ArrayList<Integer>> resultList, ArrayList<Integer> inputResult, int totalCount, ArrayList<Integer> exceptList) {
if (exceptList == null) {
exceptList = new ArrayList<Integer>();
}
for (int i=0; i<totalCount; i++) {
if (exceptList.contains(i)) {
continue;
}
ArrayList<Integer> oneResult = null;
if (exceptList.size() == 0) {
oneResult = new ArrayList<Integer>();
} else {
oneResult = (ArrayList<Integer>) inputResult.clone();
}
if (oneResult.size() < totalCount) {
oneResult.add(i);
if (oneResult.size() == totalCount) {
resultList.add(oneResult);
} else if (oneResult.size() < totalCount) {
ArrayList<Integer> newExceptList = (ArrayList<Integer>) exceptList.clone();
newExceptList.add(i);
shuffleRecursively(resultList, oneResult, totalCount, newExceptList);
}
}
}
}
}
|