ericnormand/00 Permutations of a sequence.md

## 00 Permutations of a sequence.md

      
    Raw
  

              00 Permutations of a sequence.md
            
          
    permutations of a sequence
The permutations of a sequence are all of the sequences with the same elements but in different orders. Here are some examples.
The permutations of [1, 2] are [1, 2] and [2, 1].
The permutations of [1, 2, 3] are [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].
The number of permutations grows really fast with the size of the list.
Your challenge is to write a function that generates all permutations of a list. Your function should return a lazy sequence.
Note: there already is a great, fast implementation of this function in clojure.math.combinatorics

  
## Dan Dorman.clj
(defn permutations [coll]
  (case (count coll)
    0 []
    1 [coll]
    (->> (range (count coll))
         (map #(split-at % coll))
         (mapcat (fn [[fore [target & aft]]]
                   (let [ps (permutations (concat fore aft))]
                     (map (partial cons target) ps)))))))

## Eric Normand.clj
(defn permutations [coll]
  (if (empty? coll)
    (list ())
    (->> coll
         (map-indexed (fn [t _] (split-at t coll)))
         (map (fn [[bf af]] [(first af) (concat bf (rest af))]))
         (mapcat (fn [[f rst]] (map #(cons f %) (permutations rst))))
         (distinct))))

;; with transducers
(defn vsplit [t v]
  [(get v t) (concat (subvec v 0 t) (subvec v (inc t)))])

(defn permutationst [coll]
  (if (empty? coll)
    (list [])
    (let [v (vec coll)
          tr (comp (map-indexed (fn [t _] (vsplit t v)))
                   (mapcat (fn [[f rst]] (map #(cons f %) (permutationst rst))))
                   (distinct))]
      (sequence tr v))))

## Juraj Martinka.clj
(ns clojure-experiments.purely-functional.puzzles.0341-permutations
  "https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-341-tip-tidy-up-your-ns-form/
  Write a function that returns all possible permutations of given sequence.
  Your function should return lazy sequence.
  See also `clojure.math.combinatorics/permutations`."
  (:require [clojure.test :refer [deftest is testing]]))

(defn permutations [aseq]
  #_(println "Computating permutation for " aseq)
  (cond
    (empty? aseq)
    []

    (= 1 (count aseq))
    [aseq]

    :else
    (for [x aseq
          xs (permutations (disj (set aseq)
                                 x))]
      (cons x xs))))

(take 2 (permutations [1 2 3]))
;; => ((1 3 2) (1 2 3) (2 1 3) (2 3 1) (3 1 2) (3 2 1))


(deftest permutations-test
  (testing "empty sequence"
    (is (= []
           (permutations []))))
  (testing "sequence of one"
    (is (= [[1]]
           (permutations [1]))))
  (testing "3-elements sequence have all 6 permutations"
    (let [permutations (permutations [2 1 3])]
      (is (= #{[1 2 3] [1 3 2]
               [2 1 3] [2 3 1]
               [3 1 2] [3 2 1]}
             (set permutations)))))
  (testing "many elements sequence have n! permutations"
      (let [permutations (permutations [1 2 3 4 5 10 9 8 7 6])]
        (is (= 3628800
               (count permutations))))))

## Magnus Kvalevag.clj
(defn swap
  [coll i1 i2]
  (->> coll
       (map-indexed (fn [i x]
                      (condp = i
                        i1 (nth coll i2)
                        i2 (nth coll i1)
                        x)))))

(defn permutations
  "Based on https://media.geeksforgeeks.org/wp-content/cdn-uploads/NewPermutation.gif"
  ([coll]
   (permutations coll 0))
  ([coll fixed]
   (let [unfixed (- (count coll) fixed)]
     (if (zero? unfixed)
       coll
       ((if (= 1 unfixed) map mapcat)                       ; Flatten the tree into a single list
         (fn [i]
           (permutations (swap coll fixed i) (inc fixed)))
         (range fixed (count coll)))))))

## Mark Champine.clj
(defn permutations [s]
  (lazy-seq
   (if (seq (rest s))
     (apply concat (for [x s]
                     (map #(cons x %) (permutations (remove #{x} s)))))
     [s])))

;; tests
(=  (permutations [1 2]) [[1 2] [2 1]])
(=  (permutations [1 2 3]) [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]])
(= (nth (permutations [1 2 3 4 5]) 22) [1 5 4 2 3])

(defn ! [n] (apply * (range 2 (inc n))))
(= (! 6) (count (permutations [1 2 3 4 5 6])))
(= (! 7) (count (permutations [1 2 3 4 5 6 7])))
(= (! 8) (count (permutations [1 2 3 4 5 6 7 8])))

## Venkatesh Pitta.clj
(ns permutations.core
  (:require [clojure.set])

;; https://www.topcoder.com/blog/generating-permutations/ Attempt at
;; Clojure implementation of permutation algorithms as found in this
;; TC article

(defn swap
  "Return v with elements at i1 and i2 swapped"
  [v i1 i2]
  (assoc v i2 (v i1) i1 (v i2)))

(defn- permutation01
  "Basic Algorithm 1: Remove"
  [array n]
  (if (= 1 n)
    array
    (apply concat
           (mapcat #(vector
                     (permutation01 (swap array % (dec n)) (dec n))
                     (swap array % (dec n)))
                   (range 0 (count array))))))

(defn permutation01-toplevel [array]
  (into ()
        (set
         (partition (count array)
                    (permutation01 array (count array))))))

(defn permutation-heaps
  "Heap's Algorithm -- the listing says the loop is for i from 0 to i
  > (n-1).  Could be a typo.  Or not.  Wikipedia (linked in both the
  TC article as well as the G4G article) pseudo-code seems different
  from what is on
  https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/"
  ;; incomplete/incorrect heap's algorithm, until getting my hands on
  ;; the algorithms book by Robert Sedgewick to gain a full
  ;; understanding of the algorithm
  [array n]
  (if (= 1 n)
    array
    (apply concat
           (permutation-heaps array (dec n))
           (mapcat #(vector (permutation-heaps (swap array (if (even? n) % 0) (dec n))
                                               (dec n)))
                   (range 0 n)))))

;; below is an algorithm from
;; https://github.com/shaunluttin/algorithms/blob/master/articles/functional-programs-for-generating-permutations/article.pdf
;; with Clojure implementation a simple translation from the F#
;; illustration in the same repo

;; Algorithm A
;; for each permutation p of (tl x) do
;;   insert (hd x) at each possible position in p
(defn algorithm-a [x]
  (defn put [a p q]
    (if (= p q)
      (cons a q)
      (cons (first p) (put a (rest p) q))))
  (defn insert [a p q ps]
    (if-not (seq q)
      (cons (put a p []) ps)
      (cons (put a p q) (insert a p (rest q) ps))))
  (defn map-insert [a ps]
    (if-not (seq ps)
      '()
      (insert a (first ps) (first ps) (map-insert a (rest ps)))))
  (if-not (seq x)
    '(())
    (map-insert (first x) (algorithm-a (rest x)))))
	(defn permutations [coll]
	(case (count coll)
	0 []
	1 [coll]
	(->> (range (count coll))
	(map #(split-at % coll))
	(mapcat (fn [[fore [target & aft]]]
	(let [ps (permutations (concat fore aft))]
	(map (partial cons target) ps)))))))
	(defn permutations [coll]
	(if (empty? coll)
	(list ())
	(->> coll
	(map-indexed (fn [t _] (split-at t coll)))
	(map (fn [[bf af]] [(first af) (concat bf (rest af))]))
	(mapcat (fn [[f rst]] (map #(cons f %) (permutations rst))))
	(distinct))))

	;; with transducers
	(defn vsplit [t v]
	[(get v t) (concat (subvec v 0 t) (subvec v (inc t)))])

	(defn permutationst [coll]
	(if (empty? coll)
	(list [])
	(let [v (vec coll)
	tr (comp (map-indexed (fn [t _] (vsplit t v)))
	(mapcat (fn [[f rst]] (map #(cons f %) (permutationst rst))))
	(distinct))]
	(sequence tr v))))
	(ns clojure-experiments.purely-functional.puzzles.0341-permutations
	"https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-341-tip-tidy-up-your-ns-form/
	Write a function that returns all possible permutations of given sequence.
	Your function should return lazy sequence.
	See also `clojure.math.combinatorics/permutations`."
	(:require [clojure.test :refer [deftest is testing]]))

	(defn permutations [aseq]
	#_(println "Computating permutation for " aseq)
	(cond
	(empty? aseq)
	[]

	(= 1 (count aseq))
	[aseq]

	:else
	(for [x aseq
	xs (permutations (disj (set aseq)
	x))]
	(cons x xs))))

	(take 2 (permutations [1 2 3]))
	;; => ((1 3 2) (1 2 3) (2 1 3) (2 3 1) (3 1 2) (3 2 1))


	(deftest permutations-test
	(testing "empty sequence"
	(is (= []
	(permutations []))))
	(testing "sequence of one"
	(is (= [[1]]
	(permutations [1]))))
	(testing "3-elements sequence have all 6 permutations"
	(let [permutations (permutations [2 1 3])]
	(is (= #{[1 2 3] [1 3 2]
	[2 1 3] [2 3 1]
	[3 1 2] [3 2 1]}
	(set permutations)))))
	(testing "many elements sequence have n! permutations"
	(let [permutations (permutations [1 2 3 4 5 10 9 8 7 6])]
	(is (= 3628800
	(count permutations))))))
	(defn swap
	[coll i1 i2]
	(->> coll
	(map-indexed (fn [i x]
	(condp = i
	i1 (nth coll i2)
	i2 (nth coll i1)
	x)))))

	(defn permutations
	"Based on https://media.geeksforgeeks.org/wp-content/cdn-uploads/NewPermutation.gif"
	([coll]
	(permutations coll 0))
	([coll fixed]
	(let [unfixed (- (count coll) fixed)]
	(if (zero? unfixed)
	coll
	((if (= 1 unfixed) map mapcat) ; Flatten the tree into a single list
	(fn [i]
	(permutations (swap coll fixed i) (inc fixed)))
	(range fixed (count coll)))))))
	(defn permutations [s]
	(lazy-seq
	(if (seq (rest s))
	(apply concat (for [x s]
	(map #(cons x %) (permutations (remove #{x} s)))))
	[s])))

	;; tests
	(= (permutations [1 2]) [[1 2] [2 1]])
	(= (permutations [1 2 3]) [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]])
	(= (nth (permutations [1 2 3 4 5]) 22) [1 5 4 2 3])

	(defn ! [n] (apply * (range 2 (inc n))))
	(= (! 6) (count (permutations [1 2 3 4 5 6])))
	(= (! 7) (count (permutations [1 2 3 4 5 6 7])))
	(= (! 8) (count (permutations [1 2 3 4 5 6 7 8])))
	(ns permutations.core
	(:require [clojure.set])

	;; https://www.topcoder.com/blog/generating-permutations/ Attempt at
	;; Clojure implementation of permutation algorithms as found in this
	;; TC article

	(defn swap
	"Return v with elements at i1 and i2 swapped"
	[v i1 i2]
	(assoc v i2 (v i1) i1 (v i2)))

	(defn- permutation01
	"Basic Algorithm 1: Remove"
	[array n]
	(if (= 1 n)
	array
	(apply concat
	(mapcat #(vector
	(permutation01 (swap array % (dec n)) (dec n))
	(swap array % (dec n)))
	(range 0 (count array))))))

	(defn permutation01-toplevel [array]
	(into ()
	(set
	(partition (count array)
	(permutation01 array (count array))))))

	(defn permutation-heaps
	"Heap's Algorithm -- the listing says the loop is for i from 0 to i
	> (n-1). Could be a typo. Or not. Wikipedia (linked in both the
	TC article as well as the G4G article) pseudo-code seems different
	from what is on
	https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/"
	;; incomplete/incorrect heap's algorithm, until getting my hands on
	;; the algorithms book by Robert Sedgewick to gain a full
	;; understanding of the algorithm
	[array n]
	(if (= 1 n)
	array
	(apply concat
	(permutation-heaps array (dec n))
	(mapcat #(vector (permutation-heaps (swap array (if (even? n) % 0) (dec n))
	(dec n)))
	(range 0 n)))))

	;; below is an algorithm from
	;; https://github.com/shaunluttin/algorithms/blob/master/articles/functional-programs-for-generating-permutations/article.pdf
	;; with Clojure implementation a simple translation from the F#
	;; illustration in the same repo

	;; Algorithm A
	;; for each permutation p of (tl x) do
	;; insert (hd x) at each possible position in p
	(defn algorithm-a [x]
	(defn put [a p q]
	(if (= p q)
	(cons a q)
	(cons (first p) (put a (rest p) q))))
	(defn insert [a p q ps]
	(if-not (seq q)
	(cons (put a p []) ps)
	(cons (put a p q) (insert a p (rest q) ps))))
	(defn map-insert [a ps]
	(if-not (seq ps)
	'()
	(insert a (first ps) (first ps) (map-insert a (rest ps)))))
	(if-not (seq x)
	'(())
	(map-insert (first x) (algorithm-a (rest x)))))