http://www.insightbook.co.kr/post/3855

자연수 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}가 먼저 출력되든 상관 없습니다. 빠짐없이 출력하기만 하면 됩니다.ds


구현 입니다.

n이 2인 경우에 기저 조건을 채우고, 2 이상의 n에 대해서 에 대해서 n-1을 재귀적으로 더해가는 과정을 반복합니다.

아직 clojure에 익숙하지 않아서 불필요한 코드가 많이 생겼네요. 

flat 이나 rotates같은 보조함수가 없어도 쉽게 구현이 될것 같은데 조금 더 연구가 필요할듯.


;; clojure

(defn rotates [xss] (for [idx (range (count xss))] (let [[a b & _] (split-at idx xss)] (concat b a)))) (defn flat [xss] (loop [[x & xs :as xss] xss, acc []] (cond (empty? xss) acc (= (count x) 1) (recur xs (conj acc (first x))) :else (recur xs (concat x acc))))) (defn find-sub-set [[x & xs :as xss]] (cond (= (count xss) 2) (let [[a b & _] xss] `(((~a), (~b)), ((~a, ~b)))) :else (let [subs (find-sub-set xs)] (concat (map #(cons `(~x) %) subs) (flat (map #(map (fn [[h & r]] (cons (cons x h) r)) (rotates %)) subs))))))

출력

=> 

((0) (1) (2) (3)) ((0) (1) (2 3)) ((0) (1 2) (3)) ((0) (1 3) (2)) ((0) (1 2 3)) ((0 1) (2) (3)) ((0 2) (3) (1)) ((0 3) (1) (2)) ((0 1) (2 3)) ((0 2 3) (1)) ((0 1 2) (3)) ((0 3) (1 2)) ((0 1 3) (2)) ((0 2) (1 3)) ((0 1 2 3))


      분류없음  |  2012.09.03 18:52
2013.07.28 21:55 댓글에 댓글수정/삭제
다른 남자 부르면서 울거면 나한테 이쁘지나 말던지
.
name ::   password :: blog :: secret
등록



blueiur's Blog is powered by Daum