‘문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이’

_README.md

이벤트 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으로 계산하면 대략 한 시간 반은 걸리는 것 같습니다. 한번 돌려 보곤 엄두도 못 내고 있어요. ㅠㅠ

SetPartitioner.java

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());
        }
    }
}

SetPartitionerTest.java

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 ++;
        }
    }
}