Created
February 10, 2010 23:04
-
-
Save lypanov/300947 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(use 'clojure.test) | |
(defn groups-of [n vec] | |
(cond (<= (count vec) n) [vec] | |
:else (lazy-seq (cons (subvec vec 0 n) (groups-of n (subvec vec 1)))))) | |
(defn swap [coll i j] | |
(let [ci (coll i) cj (coll j)] | |
(assoc coll i cj j ci))) | |
(defn first-matching-index | |
([pred coll] | |
(first-matching-index pred coll 0)) | |
([pred coll from-index] | |
(if-let [x (pred from-index (first coll))] x | |
(if (next coll) (first-matching-index pred (next coll) (inc from-index)))))) | |
(deftest test-first-matching-index | |
(is (= (first-matching-index (fn [idx value] (when (= 3 value) [idx value])) [1 2 3 4 5]) [2 3]))) | |
(run-tests) | |
(defn first-non-ascending-from-end [coll] | |
(when-let [idx (first-matching-index (fn [idx [a b]] (when (< a b) idx)) | |
(reverse (groups-of 2 coll)))] | |
(- (count coll) idx 2))) | |
(defn first-higher-than-from-end [num coll] | |
(when-let [idx (first-matching-index (fn [idx a] (when (> a num) idx)) | |
(reverse coll))] | |
(inc (- (count coll) idx 2)))) | |
(defn next-in-lexographical-permutation [current] | |
(if-let [i (first-non-ascending-from-end current)] | |
(if-let [j (first-higher-than-from-end (current i) current)] | |
(vec (concat (first (split-at (inc i) (swap current i j))) (reverse (second (split-at (inc i) (swap current i j)))))) | |
"nothing lower than from end") | |
nil)) | |
(defn perm-seq | |
([n] | |
(perm-seq (vec (range (inc n))) n)) | |
([current n] | |
(lazy-seq (when-let [next-in-seq (next-in-lexographical-permutation current)] (cons [current] (perm-seq next-in-seq n)))))) | |
(first (drop 999999 (perm-seq 9))) | |
(deftest test-first-non-ascending-from-end | |
(is (= nil (first-non-ascending-from-end [6 5 4 3 2 1]))) | |
(is (= 4 (first-non-ascending-from-end [1 2 3 4 5 6]))) | |
(is (= 2 (first-non-ascending-from-end [1 2 3 6 5 4]))) | |
(is (= 0 (first-non-ascending-from-end [1 6 5 4 3 2])))) | |
(deftest test-first-higher-than-from-end | |
(is (= 5 (first-higher-than-from-end 5 [1 2 3 4 5 6]))) | |
(is (= 5 (first-higher-than-from-end 3 [1 2 3 6 5 4]))) | |
(is (= 5 (first-higher-than-from-end 1 [1 6 5 4 3 2]))) | |
(is (= 4 (first-higher-than-from-end 5 [1 2 3 5 6 4])))) | |
(deftest test-next-in-lexographical-permutation-6 | |
(is (= [1 2 3 4 6 5] (next-in-lexographical-permutation [1 2 3 4 5 6]))) | |
(is (= [1 2 4 3 5 6] (next-in-lexographical-permutation [1 2 3 6 5 4]))) | |
(is (= [2 1 3 4 5 6] (next-in-lexographical-permutation [1 6 5 4 3 2]))) | |
(is (= [1 2 3 6 4 5] (next-in-lexographical-permutation [1 2 3 5 6 4])))) | |
(deftest test-next-in-lexographical-permutation-4 | |
(is (= [1 2 4 3] (next-in-lexographical-permutation [1 2 3 4]))) | |
(is (= nil (next-in-lexographical-permutation [4 3 2 1]))) | |
(is (= [4 3 1 2] (next-in-lexographical-permutation [4 2 3 1]))) | |
(is (= [3 4 1 2] (next-in-lexographical-permutation [3 2 4 1]))) | |
(is (= [1 4 3 2] (next-in-lexographical-permutation [1 4 2 3])))) | |
(run-tests) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment