quarta-feira, 8 de fevereiro de 2012

Clojure composition and spirit binding

These days I had to craft something that I didn't even knew existed (don't you love when this happens?). Number composition is the name of the spirit this time.

I will paste the algorithm in clojure below, but I guess the most important thing regarding spirits is not the ritual to bind them, but how you find their names so you can research the ritual itself. My favorite source of arcana regarding spirit names is [1]. I advice it to any wizard, be they apprendice or warlock.

Well, here it goes my version of the ritual, hope you enjoy it.

(defn generate-compositions [num]
  "Returns all possible valid partitions of an integer. An useful

* Skiena's The Algorithm Design Manual, section 14.6 Generating Partitions.

* http://code.activestate.com/recipes/218332/

* http://stackoverflow.com/questions/8375439/composition-algorithm-in-javascript-to-return-all-possible-compositions-of-a-num

This will run in O(2^n), so take care with large inputs."
  (defn accumulate-reduced-compositions
       (accumulate-reduced-compositions composition-set 0 [] (count composition-set)))
    ([composition-set index acc set-lenght]
       (let [next-index (inc index)]
         (if (>= next-index set-lenght)
           (recur composition-set
                  (conj acc (into (conj (subvec composition-set 0 index)
                                        (+ (nth composition-set index)
                                           (nth composition-set next-index)))
                                  (subvec composition-set (inc next-index))))
  (loop [all-compositions [(vec (repeat num 1))]
         new-compositions (accumulate-reduced-compositions (first all-compositions))]
    (let [first-new-composition (first new-compositions)]
      (if (= 1 (count first-new-composition))
        (set (conj all-compositions first-new-composition))
        (recur (into all-compositions new-compositions)
               (reduce into (map accumulate-reduced-compositions new-compositions)))))))

[1] Steven Skiena: The Algorithm Design Manual

Nenhum comentário:

Postar um comentário