Skip to content

Instantly share code, notes, and snippets.

@fupfin
Created September 7, 2012 10:57
Show Gist options
  • Save fupfin/3665093 to your computer and use it in GitHub Desktop.
Save fupfin/3665093 to your computer and use it in GitHub Desktop.
‘문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이’

이벤트 1주차 두 번째 문제를 풀어 봅니다.

문제

자연수 n을 입력받아 집합 {0, 1, 2, …, n-1}을 하나 이상의 집합으로 나누는 방법을 모두 출력하는 프로그램을 작성하세요.

###실행 예

input n: 3{0, 1, 2}{0} {1, 2}{1} {0, 2}{2} {0, 1}{0} {1} {2}

###참고

  1. n의 범위는 크게 상관이 없지만, 대략 16 이하라고 가정하시면 되겠습니다. ^^
  2. 집합으로 나눈 경우를 출력하는 방법은 상관없습니다.
    • {1} {0, 2}를 {0, 2} {1}로 표현해도 되고, 1, 0 2로 표현해도 됩니다. (다른 형식도)- 또, {0} {1, 2}가 먼저 출력되든, {0} {1} {2}가 먼저 출력되든 상관 없습니다. 빠짐없이 출력하기만 하면 됩니다.

풀이

이 문제는 0부터 n-1까지의 숫자로 구성된 집합에서 얼마나 다양한 조합의 묶음이 가능한지 찾는 문제입니다.

저는 0부터 n-1까지의 숫자를 묶을 때 정렬을 할 경우 중복을 제거할 수 있다는 점에 착안해 다음과 같은 순서로 모든 조합을 찾아 내도록 했습니다.

  1. 0부터 n-1까지의 수 하나로 구성된 묶음의 집합을 만든다.

    {0} {1} {2}

  2. 집합의 처음 묶음을 선택해 나머지 묶음과 차례대로 합해 여러 조합을 찾는다. 이 때 두 묶음이 합쳐졌을 때 묶음 안의 숫자가 올림차순으로 정렬이 안 된다면 묶지 않는다.

    {0, 1} {2} {0, 2} {1}

  3. 2의 결과로 나온 조합에서 2를 반복한다.

    {0, 1, 2}

  4. 처음 묶음으로 나머지 묶음과 합해 모든 조합을 찾았다면 첫 묶음을 고정으로 놔 두고 두번째 묶음과 그 뒤 묶음을 가지고 2를 반복한다.

    {0} {1, 2}

테스트는 집합 크기에 대한 결과는 Bell Number를 이미 알고 있으므로 테스트가 가능합니다. 코드는 main() 메서드도 포함하는 바람에 좀 깁니다.

실행하는 방법은 다음과 같습니다.

$ java org.fupfin.insight.event2.SetPartitioner 15
Bell number for 15 : 1382958545
Run time: 195.407 secs

결과를 모두 찍고 싶으면 -v 옵션을 추가합니다.

$ java org.fupfin.insight.event2.SetPartitioner -v 4
{0}{1}{2}{3}
{0, 1}{2}{3}
{0, 1, 2}{3}
{0, 1, 2, 3}
{0, 1, 3}{2}
{0, 1}{2, 3}
{0, 2}{1}{3}
{0, 2, 3}{1}
{0, 2}{1, 3}
{0, 3}{1}{2}
{0, 3}{1, 2}
{0}{1, 2}{3}
{0}{1, 2, 3}
{0}{1, 3}{2}
{0}{1}{2, 3}
Bell number for 4 : 15
Run time: 0.004 secs

P.S 문제 풀이는 지난 주말에 했는데 멀티 코어에서 돌리려고 ForkJoinPool도 적용하고 여러가지 리펙터링도 시도해보다가 늦게 올립니다. 사실 지금 올리는 것도 최종 버전은 아닌...;;; P.S#2 16으로 계산하면 대략 한 시간 반은 걸리는 것 같습니다. 한번 돌려 보곤 엄두도 못 내고 있어요. ㅠㅠ

package org.fupfin.insight.event1b;
import java.util.Arrays;
import java.util.concurrent.RecursiveAction;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
public class SetPartitioner {
ForkJoinPool pool = new ForkJoinPool();
public void partition(int n, ResultHandler handler) {
pool.invoke(new Partitioner(new int[0][], generateSet(n), handler));
}
@SuppressWarnings("serial")
class Partitioner extends RecursiveAction{
private static final int FORK_THRESHOLD = 10;
private int[][] initialPrefix;
private int[][] initialWorkSet;
private ResultHandler handler;
Partitioner(int[][] prefix, int[][] workSet, ResultHandler handler) {
this.initialPrefix = prefix;
this.initialWorkSet = workSet;
this.handler = handler;
}
@Override
protected void compute() {
partition(this.initialPrefix, this.initialWorkSet);
}
private void partition(int[][] prefix, int[][] workSet) {
handler.handle(prefix, workSet);
discoverSubPartitions(prefix, workSet);
}
private void discoverSubPartitions(int[][] prefix, int[][] workSet) {
while(workSet.length > 1) {
int[] head = workSet[0];
int[][] tail = Arrays.copyOfRange(workSet, 1, workSet.length);
composeNewPartitionAndDiscover(prefix, head, tail);
prefix = mergeLists(prefix, new int[][]{head});
workSet = tail;
}
}
private void composeNewPartitionAndDiscover(int[][] prefix, int[] first, int[][] rest) {
List<Partitioner> subtasks = new LinkedList<Partitioner>();
int mostHighestNumber = first[first.length - 1];
for(int j = 0; j < rest.length; j++) {
if(rest[j][0] <= mostHighestNumber)
continue;
int[] second = rest[j];
int[][] nextWorkingSet = mergeLists(
new int[][]{unite(first, second)},
Arrays.copyOfRange(rest, 0, j),
Arrays.copyOfRange(rest, j+1, rest.length));
if(nextWorkingSet.length < FORK_THRESHOLD)
partition(prefix, nextWorkingSet);
else {
subtasks.add(new Partitioner(prefix, nextWorkingSet, this.handler));
}
}
if(subtasks.size() > 0)
invokeAll(subtasks);
}
}
private int[] unite(int[] first, int[] second) {
int[] union = new int[first.length + second.length];
System.arraycopy(first, 0, union, 0, first.length);
System.arraycopy(second, 0, union, first.length, second.length);
return union;
}
private int[][] mergeLists(int[][] ... lists) {
int len = 0;
for(int[][] list: lists)
len += list.length;
int[][] result = new int[len][];
int idx = 0;
for(int[][] list:lists) {
System.arraycopy(list, 0, result, idx, list.length);
idx += list.length;
}
return result;
}
private int[][] generateSet(int n) {
int[][] result = new int[n][];
for(int i=0; i < n; i++)
result[i] = new int[]{i};
return result;
}
static interface ResultHandler {
public void handle(int[][] prefix, int[][] rest);
}
public static void main(String[] args) {
Counter counter = new Counter();
ResultHandler handler = new SilenceResultHandler(counter);
int setSize = 0;
if(args.length <= 0) {
printUsage();
return;
}
if(args.length > 1) {
if(args[0].equals("-v"))
handler = new SetPrintingResultHandler(counter);
else if(args[0].equals("-d"))
handler = new DotPrintingResultHandler(counter);
else {
printUsage();
return;
}
}
Long startTime = System.currentTimeMillis();
setSize = Integer.valueOf(args[args.length > 1 ? 1 : 0]);
new SetPartitioner().partition(setSize, handler);
System.out.println("Bell number for " + setSize + " : " + counter.count);
System.out.println("Run time: " + (System.currentTimeMillis() - startTime) / 1000.0 + " secs");
}
private static void printUsage() {
System.out.println("java SetPartitioner [-v|-d] set_size\n" +
"\t-v: verbose output\n" +
"\t-d: dot pregression output\n" +
"\tset_size : size of set. greater than 0");
}
static class Counter {
long count;
synchronized void inc() {
count ++;
}
}
static class SilenceResultHandler implements ResultHandler {
private Counter counter;
public SilenceResultHandler(Counter counter) {
this.counter = counter;
}
public void handle(int[][] prefix, int[][] rest) {
this.counter.inc();
}
}
static class DotPrintingResultHandler implements ResultHandler {
private Counter counter;
public DotPrintingResultHandler(Counter counter) {
this.counter = counter;
}
@Override
public synchronized void handle(int[][] prefix, int[][] rest) {
if(counter.count % 100000 == 0) {
System.out.print("\n"); System.out.print(counter.count); System.out.print(": ");
}
if(counter.count % 1000 == 0)
System.out.print('.');
counter.inc();
}
}
static class SetPrintingResultHandler implements ResultHandler {
private Counter counter;
public SetPrintingResultHandler(Counter counter) {
this.counter = counter;
}
public synchronized void handle(int[][] prefix, int[][] rest) {
this.counter.inc();
printResult(prefix);
printResult(rest);
System.out.println("");
}
private void printResult(int[][] result) {
StringBuilder buf = new StringBuilder();
for(int i=0; i<result.length; i++) {
int[] set = result[i];
buf.append('{');
for(int j=0; j<set.length; j++)
buf.append(j > 0 ? ", " : "").append(set[j]);
buf.append('}');
}
System.out.print(buf.toString());
}
}
}
package org.fupfin.insight.event1b;
import static org.junit.Assert.*;
import org.junit.Test;
public class SetPartitionerTest {
Counter counter = new Counter();
SetPartitioner partitioner = new SetPartitioner();
SetPartitioner.ResultHandler resultHandler = new SetPartitioner.ResultHandler() {
public synchronized void handle(int[][] prefix, int[][] rest) {
counter.inc();
}
};
@Test
public void 개수1은_집합이_하나() {
partitioner.partition(1, resultHandler);
assertEquals(1, counter.count);
}
@Test
public void 알고_있는_개수_확인() {
int[] nums = {2, 3, 4, 5, 6, 7, 8, 9};
int[] numPartitions = {2, 5, 15, 52, 203, 877, 4140, 21147}; //16은 10480142147L
for(int i = 0; i < nums.length; i++) {
counter.count = 0;
partitioner.partition( nums[i], resultHandler);
assertEquals(numPartitions[i], counter.count);
}
}
static class Counter {
long count = 0;
synchronized void inc() {
count ++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment