Anonymous user
Permutations/Derangements: Difference between revisions
Derangements in Clojure
(Derangements in Clojure) |
|||
Line 865:
}
</lang>
=={{header|Clojure}}==
Generating functions with no fixed point
<lang Clojure>(ns derangements.core
(:require [clojure.set :as s]))
(defn subfactorial [n]
(case n
0 1
1 0
(* (dec n) (+ (subfactorial (dec n)) (subfactorial (- n 2))))))
(defn no-fixed-point
"f : A -> B must be a biyective function written as a hash-map, returns
all g : A -> B such that (f(a) = b) => not(g(a) = b)"
[f]
(case (count f)
0 [{}]
1 []
(let [g (s/map-invert f)
a (first (keys f))
a' (f a)]
(mapcat
(fn [b'] (let [b (g b')
f' (dissoc f a b)]
(concat (map #(reduce conj % [[a b'] [b a']])
(no-fixed-point f'))
(map #(conj % [a b'])
(no-fixed-point (assoc f' b a'))))))
(filter #(not= a' %) (keys g))))))
(defn derangements [xs]
{:pre [(= (count xs) (count (set xs)))]}
(map (fn [f] (mapv f xs))
(no-fixed-point (into {} (map vector xs xs)))))
(defn -main []
(do
(doall (map println (derangements [0,1,2,3])))
(doall (map #(println (str (subfactorial %) " " (count (derangements (range %)))))
(range 10)))
(println (subfactorial 20))))
</lang>
{{Out}}
<pre>[1 0 3 2]
[1 2 3 0]
[1 3 0 2]
[2 3 0 1]
[2 3 1 0]
[2 0 3 1]
[3 2 1 0]
[3 2 0 1]
[3 0 1 2]
1 1
0 0
1 1
2 2
9 9
44 44
265 265
1854 1854
14833 14833
133496 133496
895014631192902121</pre>
=={{header|D}}==
| |||