Tuesday, June 21, 2011

Nested upto

A simple upto function might look like this:

(defn upto
  "Get the numbers from 1 to n."
  [n]

  (range 1 (inc n)))

This can be extended to a nested upto function:

(defn nested-upto
  "Compute the numbers upto n nested by k."
  [n k]

  (cond
   (= k 0) 1
   (= k 1) n   
   :else (map #(nested-upto % (dec k)) (range 1 (inc n)))))

Here is upto 5 at different levels of nesting to show what I mean:

(1 2 3 4 5)

((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5))

(((1))
 ((1) (1 2))
 ((1) (1 2) (1 2 3))
 ((1) (1 2) (1 2 3) (1 2 3 4))
 ((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5)))

The multichoose function I talked about previously can now be implemented using nested ranges:

(defn multichoose
  [n k]
  (apply + (flatten (list (nested-upto n k)))))

This demonstrates this basic mathematical principle.

No comments:

Post a Comment

Post a Comment