[개념 정리] 순열, 조합, 부분집합

이번 글에서는 모든 경우의 수를 탐색하는 완전탐색 기법에서 순열과 조합 그리고 부분집합에 대한 구현 방법을 정리해보고자 합니다.

순열

순열은 N개의 원소 중에서 R개의 원소를 통해 순서를 가진 부분집합을 만드는 경우의 수입니다. 순열은 재귀 함수를 통해 모든 경우의 수를 구할 수 있습니다. 

재귀함수를 사용하게 되면 이번 순서의 원소를 사용하는지 체크하는 과정이 필요한데, 이 과정은 boolean 배열을 통해 체크하거나 비트 마스킹을 통해 구현할 수 있습니다.

Boolean 배열 사용

permutationByBoolean(0);

static void permutationByBoolean(int cnt) {
		
	if (cnt == N) {
		printPermutation();
		return;
	}
	for (int i = 0; i < arr.length; i++) {
		if (check[i]) continue;
		check[i] = true;
		perm[cnt] = arr[i];
		permutationByBoolean(cnt + 1);
		check[i] = false;
	}
}

 

비트 마스킹 사용

permutationByBitmasking(0, 0);

static void permutationByBitmasking(int cnt, int flag) {
	if (cnt == N) {
		printPermutation();
		return;
	}
	for (int i = 0; i < arr.length; i++) {
		if ((flag & 1 << i) > 0)
			continue;
		perm[cnt] = arr[i];
		permutationByBitmasking(cnt + 1, flag | 1 << i);
	}
}

 

만약 오름차순으로 정렬된 배열에서 사전순으로 순열을 구하는 경우에는 다음 순서의 순열을 구하는 방법도 존재합니다. Python, C++에서는 Next Permutation이라는 라이브러리 함수를 통해 이를 제공하지만 자바는 존재하지 않기 때문에 직접 구현해 본 코드는 다음과 같습니다.

do {
	System.out.println(Arrays.toString(arr));
} while(nextPermutation());

static boolean nextPermutation() {
	int srcIdx = arr.length;
	while(--srcIdx > 0) {
		if (arr[srcIdx] >  arr[srcIdx - 1]) break;
	}
	if (--srcIdx == -1) 
		return false;
	
	int destIdx = arr.length;
	while(--destIdx >= 0) {
      if (arr[srcIdx] >= arr[destIdx])  continue;
          swap(srcIdx, destIdx);
          break;
		}
	} 
	
	destIdx = arr.length;
	while (++srcIdx < --destIdx) {
		swap(srcIdx, destIdx);
	}
	return true;
}

간단하게 과정을 설명하면 다음과 같습니다.

1. 맨 뒤에서부터 탐색을 시작해서 값이 감소하는 지점을 srcIdx로 지정
2. 맨 뒤에서부터 탐색을 시작해서 srcIdx보다 값이 첫 번째 원소와 swap
3. srcIdx 뒤의 원소를 오름차순으로 정렬

---

조합

조합은 N개의 원소 중에서 R개의 원소를 통해 부분집합을 만드는 경우의 수입니다. 순열과 다른 점은 순서에 상관없이 중복 여부를 따지기 떄문에 1,2,3 / 3,2,1과 같은 경우는 조합에서는 같은 경우가 됩니다. 조합도 재귀 함수를 통해 모든 경우의 수를 구할 수 있지만 순열과 다른 점은 재귀 함수 내부에서 for를 호출할 필요없이 다음 단계로 넘어가서 검사를 진행합니다.

combination(0, 0);

static void combination(int idx, int cnt) {
	if (cnt == N) {
		printArray();
		return;
	}
	if (idx == arr.length) return;
	
	check[idx] = true;
	combination(idx + 1, cnt + 1);
	check[idx] = false;
	combination(idx + 1, cnt);
}

 

boolean 배열를 통해 사용여부를 체크하는 방법 이외에도 직접 배열을 유지하면서 뽑은 조합을 확인할 수도 있습니다.

combinationUsingList(0, new ArrayList<Integer>());
static void combinationUsingList(int idx, ArrayList<Integer> comb) {
	if (comb.size() == N) {
		comb.forEach(e -> System.out.print(e + " "));
		System.out.println();
		return;
	}
	if (idx == arr.length) return;
	
	comb.add(arr[idx]);
	combinationUsingList(idx + 1, comb);
	comb.remove(Integer.valueOf(arr[idx]));
	combinationUsingList(idx + 1, comb);
}

 

또한, 순열을 구하는 한 방법인 Next Permutation을 통해 조합을 구할 수 있습니다. 

flag = new int[5];
int idx = arr.length;
while (N-- > 0)
	flag[--idx] = 1;

do {
	printCombination();
} while (nextPermutation());

static boolean nextPermutation() {
	int srcIdx = arr.length;
	while (--srcIdx > 0) {
		if (flag[srcIdx] > flag[srcIdx - 1])
			break;
	}
	srcIdx -= 1;
	if (srcIdx == -1)
		return false;

	int destIdx = arr.length;
	while (--destIdx >= 0) {
		if (flag[srcIdx] >= flag[destIdx])
			continue;
		swap(srcIdx, destIdx);
		break;
	}

	destIdx = arr.length;
	while (++srcIdx < --destIdx) {
		swap(srcIdx, destIdx);
	}

	return true;
}

private static void printCombination() {
	for (int i = 0; i < flag.length; i++) {
		if (flag[i] == 0)
			continue;
		System.out.print(arr[i] + " ");
	}
	System.out.println();
}

과정을 간단히 설명하면 다음과 같습니다.

1. 전체 원소(N) 만큼 배열을 만들어 0으로 초기화 한 후, 뽑을 개수(R) 만큼 뒤에서부터 1로 변경
2. Next Permutation을 통해 생성된 배열에서 1의 위치는 뽑을 원소의 위치와 동일 

---

부분 집합

부분 집합은 N개의 원소를 가지는 집합에서 원소를 사용해 만들 수 있는 모든 집합을 나타내는 경우의 수입니다. 부분 집합을 구하는 방법은 재귀를 통해 구현하는 방법과 nC1 ~ nCr을 통해 구하는 방법이 존재합니다.

subset(0, 0);
private static void subset(int i, int cnt) {
	if (i == 5) {
		System.out.println(Arrays.toString(check));
		return;
	}

	check[i] = true;
	subset(i + 1, cnt + 1);
	check[i] = false;
	subset(i + 1, cnt);
}

조합과 다른 점은 조합은 R개를 뽑지 못한 경우는 제외하였지만 부분집합은 idx가 끝에 도달하면 경우의 수에 추가한다는 부분입니다.

조합을 통해 구현

private static void combination(int idx, int cnt, int R) {
	if (cnt == R) {
		System.out.println(Arrays.toString(check));
		return;
	}
	if (idx == 5) return;

	check[idx] = true;
	combination(idx + 1, cnt + 1, R);
	check[idx] = false;
	combination(idx + 1, cnt, R);
}