Skip to content

Instantly share code, notes, and snippets.

@latant
Created March 28, 2021 21:21
Show Gist options
  • Save latant/44995023119d07cf873a2fe81019119d to your computer and use it in GitHub Desktop.
Save latant/44995023119d07cf873a2fe81019119d to your computer and use it in GitHub Desktop.
Colexicographic order in Clojure
(defn first-index [f coll]
(->> (map-indexed vector coll)
(filter (comp f second))
(map first)
(first)))
(defn first-incable [v]
(or
(first-index
(fn [[a b]] (< (inc a) b))
(map vector v (rest v)))
(dec (count v))))
(defn colex-next [v]
(let [i (first-incable v)]
(->> (update (vec (drop i v)) 0 inc)
(concat (take i (rest (range))))
(vec))))
(defn colex-seq [v]
(lazy-seq (cons v (colex-seq (colex-next v)))))
(defn colex-order [n]
(colex-seq (vec (range 1 (inc n)))))
(assert
(= (take 10 (colex-order 3))
[[1 2 3]
[1 2 4]
[1 3 4]
[2 3 4]
[1 2 5]
[1 3 5]
[2 3 5]
[1 4 5]
[2 4 5]
[3 4 5]]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment