구독하던 인사이트 출판사 블로그에서 이벤트를 하는 것을 발견하고, 간만에 알고리즘 문제에 도전~
문제는 블로그에서 확인할 수 있듯이, 주어진 집합을 하나이상의 집합으로 나누는 모든 방법을 출력하는 것이다.
뭔가, 효율적으로 이를 구하는 방법이 존재할 것 같아서 계속 고민해 봤으나, 원초적인 알고리즘을 만드는 일을 수학자가 할 일이라고 생각해서, 그냥 딱 떠오르는 방법으로 코딩 해 버렸다.
1. 입력 받은 N으로 리스트를 집합을 구한다. makelist/1
2. 1에서 만든 집합에서, 가능한 모든 부분집합을 구한다. subsets/1
3. 2에서 구한 부분집합의 조합 중, 각 원소가 한 개씩만 존재하는 조합만 고른다. combinations/1
평소 사용하던 언어로 하는 것은 시시할 것 같아, 도무지 사용할 일이 없을 것 같았던 Erlang으로 시도. 머리가 더 아팠다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
-module(insight). -export([combinations/1]). % decimal_to_bitlist decimal_to_bitlist(D, L) when D < 2 -> [D | L]; decimal_to_bitlist(D, L) -> decimal_to_bitlist(D div 2, [D rem 2 | L]). decimal_to_bitlist(D) -> decimal_to_bitlist(D, []). % expand_list expand_list(L, N) when length(L) < N -> expand_list([0 | L], N); expand_list(L, _) -> L. % bitmask_list bitmask_list(BitMask, L) -> BitMaskList = expand_list(decimal_to_bitlist(BitMask), length(L)), {TrueList, _} = lists:partition( fun({Bit, _}) -> Bit == 1 end, lists:zip(BitMaskList, L)), lists:map(fun({_, Elm}) -> Elm end, TrueList). % get every possible subsets from L subsets(_, Subsets, 0) -> Subsets; subsets(L, Subsets, BitMask) -> subsets(L, [bitmask_list(BitMask, L) | Subsets], BitMask - 1). subsets(L) -> subsets(L, [], round(math:pow(2, length(L))) - 1). % exclude subsets from Lists include any of items in Items exclude(Lists, Items) -> lists:filter( fun(L) -> lists:all( fun(Item) -> case lists:member(Item, L) of true -> false; false -> true end end, lists:flatten(Items)) end, Lists). % makelist makelist(N, L) when N >= 0 -> makelist(N - 1, [N | L]); makelist(_, L) -> L. makelist(N) -> makelist(N - 1, []). % combinations combinations([], Comb, N) -> ElemNum = length(lists:umerge(Comb)), if ElemNum > 0, ElemNum >= N -> io:format("~w~n", [Comb]); true -> ok end; combinations(Subsets, Comb, N) -> [H | T] = Subsets, Rem = exclude(T, H), combinations(Rem, [H | Comb], N), combinations(T, Comb, N). combinations(N) -> L = makelist(N), combinations(subsets(L), [], length(L)). |
출력예
1> c(insight).
{ok,insight}
2> insight:combinations(3).
[[0],[1],[2]]
[[0,1],[2]]
[[0,2],[1]]
[[0],[1,2]]
[[0,1,2]]
ok
3> insight:combinations(4).
[[0],[1],[2],[3]]
[[0,1],[2],[3]]
[[0,2],[1],[3]]
[[0],[1,2],[3]]
[[0,1,2],[3]]
[[0,3],[1],[2]]
[[0],[1,3],[2]]
[[0,1,3],[2]]
[[0],[1],[2,3]]
[[0,1],[2,3]]
[[0,2,3],[1]]
[[0,2],[1,3]]
[[0,3],[1,2]]
[[0],[1,2,3]]
[[0,1,2,3]]
ok
4>
중요: Erlang은 인사이트의 책으로 처음 배웠다.