## 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.