Skip to content

Instantly share code, notes, and snippets.

@eungju
Created August 31, 2012 07:31
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save eungju/3549899 to your computer and use it in GitHub Desktop.
문제로 풀어보는 알고리즘 149쪽 문제 3.c 풀이
-module(p1_2).
-compile(export_all).
s([_]=L) ->
[[L]];
s([A|L]) ->
S = s(L),
lists:append([lists:map(fun(X) -> [[A]|X] end, S)|lists:map(fun(X) -> each_append(A,X) end, S)]).
each_append(_, [], _, Acc) ->
Acc;
each_append(A, [H|L], Prefix, Acc) ->
each_append(A, L, [H|Prefix], [lists:append(L,[[A|H]|Prefix])|Acc]).
each_append(A, L) ->
each_append(A, L, [], []).
solve(N) ->
s(lists:seq(0, N - 1)).

문제로 풀어보는 알고리즘

우선 원소가 하나인 경우부터 생각해보자.

s({0}) = {{{0}}}

원소가 하나인 집합의 공집합을 제외한 부분집합은 하나뿐이고, 고로 나누는 방법도 하나 뿐이다.

다음 원소가 둘인 경우를 생각해보자.

s({0,1}) = {
	{{0}, {1}},
	{{0,1}}
}

위를 보면 원소가 하나인 경우의 해 {{{0}}}에다 새 집합 {1}을 추가하는 경우와, 기존 집합 {0}에 1을 원소로 추가하는 경우가 있음을 알 수 있다.

위에서 발견한 규칙을 원소가 셋인 경우에 적용해보자. 원소가 둘인 경우 위의 결과를 보면 두 가지 방법으로 나눌 수 있다. 우선 각 방법에 새 집합 {2}를 추가한다.

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

기존 집합에 새 원소로 2를 추가한다. {{0}, {1}}에 2를 추가하는 방법은 두 가지이다.

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

{{0,1}}에 2를 추가하는 방법은 한 가지이다.

{{0,1,2}}

이를 모두 합하면 다음과 같은 결과가 나온다.

s({0,1,2}) = {
	{{0},{1},{2}},
	{{0,1},{2}},
	{{0,2},{1}},
	{{0},{1,2}},
	{0,1,2}
}

이를 일반화하여 Erlang 코드로 표한하면 다음과 같다.

s([_]=L) ->
    [[L]];
s([A|L]) ->
    S = s(L),
    lists:append([lists:map(fun(X) -> [[A]|X] end, S)|lists:map(fun(X) -> each_append(A,X) end, S)]).

each_append(_, [], _, Acc) ->
    Acc;
each_append(A, [H|L], Prefix, Acc) ->
    each_append(A, L, [H|Prefix], [lists:append(L,[[A|H]|Prefix])|Acc]).

each_append(A, L) ->
    each_append(A, L, [], []).

문제에서는 n이 주어지면 0부터 n-1까지의 숫자가 원소가 된다. 주어진 문제를 풀기 위한 코드는 다음과 같다.

-module(p1_2).
-compile(export_all).

s([_]=L) ->
    [[L]];
s([A|L]) ->
    S = s(L),
    lists:append([lists:map(fun(X) -> [[A]|X] end, S)|lists:map(fun(X) -> each_append(A,X) end, S)]).

each_append(_, [], _, Acc) ->
    Acc;
each_append(A, [H|L], Prefix, Acc) ->
    each_append(A, L, [H|Prefix], [lists:append(L,[[A|H]|Prefix])|Acc]).

each_append(A, L) ->
    each_append(A, L, [], []).

solve(N) ->
    s(lists:seq(0, N - 1)).

n이 4이면 다음과 같이 15가지 방법으로 나눌 수 있다.

3> p1_2:solve(4).
[[[0],[1],[2],[3]],
 [[0],[1],[2,3]],
 [[0],[1,3],[2]],
 [[0],[3],[1,2]],
 [[0],[1,2,3]],
 [[0,3],[2],[1]],
 [[3],[0,2],[1]],
 [[2],[3],[0,1]],
 [[0,2,3],[1]],
 [[2,3],[0,1]],
 [[0,2],[1,3]],
 [[2],[0,1,3]],
 [[0,1,2],[3]],
 [[1,2],[0,3]],
 [[0,1,2,3]]]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment