글쓴이: mengpa (시티헌터)
날 짜: Tue Mar 24 02:12:01 1998
제 목: 참... 숙제에 대해서
제일 첫문제, distinct part들로 이루어진 partition을 구하는 문제에서요,
머리를 써서(?) 정확한 알고리즘을 생각해내는 것인지,
아니면 partition들을 모두 generate해서 그 중에서 distinct 여부를 check하는
무식한 방법을 써도 되는지...?
혹시, generating function으로도 가능한지...? (갯수만 세니까 안되나?)
참고로, 저는
distpart:= proc(n)
# before: 방금전에 만든 partition,
after:= nextpartition(before, n);
if nops(after) = nops({op(after)}) then print(after) fi;
# ...
end;
처럼 했거든요? 즉 list를 set으로 바꿔서 갯수를 비교한 거죠.
그러면 partition 구하는 알고리즘과 거의 다를 것이 없군요.
그래도 될까요? 아니면 깔끔한 .. 알고리즘이 존재?
사실, partition 구하는 알고리즘을 구현하는 것도 제법 고생했죠.
책의 code는 너무 보기 힘들더군요...
-- 깜
