알고리즘 코딩 이벤트 1주차 2번째 문제

저도 수동 트랙백 […]
http://sungkm.com/4736020

좋아요좋아요

수동 트랙백 입니다 🙂
http://blueiur.tistory.com/63

좋아요좋아요

기한을 못 보고 한 없이 여유 부렸네요. 의미 없지만 일단 풀었으니 올립니다. .gist table { margin-bottom: 0; } 이벤트 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}

###참고 n의 범위는 크게 상관이 없지만, 대략 16 이하라고 가정하시면 되겠습니다. ^^ 집합으로 나눈 경우를 출력하는 방법은 상관없습니다. {1} {0, 2}를 {0, 2} {1}로 표현해도 되고, 1, 0 2로 표현해도 됩니다. (다른 형식도)- 또, {0} {1, 2}가 먼저 출력되든, {0} {1} {2}가 먼저 출력되든 상관 없습니다. 빠짐없이 출력하기만 하면 됩니다. 풀이 이 문제는 0부터 n-1까지의 숫자로 구성된 집합에서 얼마나 다양한 조합의 묶음이 가능한지 찾는 문제입니다. 저는 0부터 n-1까지의 숫자를 묶을 때 정렬을 할 경우 중복을 제거할 수 있다는 점에 착안해 다음과 같은 순서로 모든 조합을 찾아 내도록 했습니다. 0부터 n-1까지의 수 하나로 구성된 묶음의 집합을 만든다. {0} {1} {2} 집합의 처음 묶음을 선택해 나머지 묶음과 차례대로 합해 여러 조합을 찾는다. 이 때 두 묶음이 합쳐졌을 때 묶음 안의 숫자가 올림차순으로 정렬이 안 된다면 묶지 않는다. {0, 1} {2} {0, 2} {1} 2의 결과로 나온 조합에서 2를 반복한다. {0, 1, 2} 처음 묶음으로 나머지 묶음과 합해 모든 조합을 찾았다면 첫 묶음을 고정으로 놔 두고 두번째 묶음과 그 뒤 묶음을 가지고 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으로 계산하면 대략 한 시간 반은 걸리는 것 같습니다. 한번 돌려 보곤 엄두도 못 내고 있어요. ㅠㅠ view raw _README.md hosted with ❤ by GitHub This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters 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_sizen" + "t-v: verbose outputn" + "t-d: dot pregression outputn" + "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()); } } } view raw SetPartitioner.java hosted with ❤ by GitHub This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters 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 ++; } } } view raw SetPartitionerTest.java hosted with ❤ by GitHub 좋아요좋아요