lazy-seqs.clj: add rotations and permutations

1 files changed, 37 insertions, 10 deletions

diff --git a/lazy-seqs.clj b/lazy-seqs.clj
index 34cfc84c..7891bcfa 100644
--- a/lazy-seqs.clj
+++ b/lazy-seqs.clj
@@ -1,14 +1,14 @@
-;;  Copyright (c) Stephen C. Gilardi. All rights reserved.
-;;  The use and distribution terms for this software are covered by the
-;;  Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
-;;  which can be found in the file CPL.TXT at the root of this distribution.
-;;  By using this software in any fashion, you are agreeing to be bound by
-;;  the terms of this license.
-;;  You must not remove this notice, or any other, from this software.
+;;  Copyright (c) Stephen C. Gilardi. All rights reserved. The use and
+;;  distribution terms for this software are covered by the Common Public
+;;  License 1.0 (http://opensource.org/licenses/cpl.php) which can be found
+;;  in the file CPL.TXT at the root of this distribution. By using this
+;;  software in any fashion, you are agreeing to be bound by the terms of
+;;  this license. You must not remove this notice, or any other, from this
+;;  software.
 ;;
 ;;  lazy-seqs.clj
 ;;
-;;  Lazy sequences
+;;  == Lazy sequences ==
 ;;
 ;;  primes - based on the "naive" implemention described in [1] plus a
 ;;           small "wheel" which eliminates multiples of 2, 3, 5, and
@@ -19,12 +19,18 @@
 ;;
 ;;  powers-of-2 - all the powers of 2
 ;;
+;;  == Lazy sequence functions ==
+;;
+;;  rotations - returns a lazy seq of all the rotations of a seq
+;;
+;;  permutations - returns a lazy seq of all the permutations of a seq
+;;
 ;;  [1] http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
 ;;  [2] http://clj-me.blogspot.com/2008/06/primes.html
 ;;  [3] http://en.wikibooks.org/wiki/Clojure_Programming#Examples
 ;;
 ;;  scgilardi (gmail)
-;;  07 June 2008
+;;  Created 07 June 2008
 
 (clojure/in-ns 'lazy-seqs)
 (clojure/refer 'clojure)
@@ -35,7 +41,8 @@
   (lazy-cat [2 3 5 7]
     (let [primes-from
           (fn primes-from [n [f & r]]
-            (if (some #(zero? (rem n %)) (take-while #(<= (* % %) n) primes))
+            (if (some #(zero? (rem n %))
+                      (take-while #(<= (* % %) n) primes))
               (recur (+ n f) r)
               (lazy-cons n (primes-from (+ n f) r))))
           wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6  4  2
@@ -61,3 +68,23 @@
               (lazy-cons next (rest-fn next))))]
       (rest-fn 1)))
   "A lazy sequence of all the powers of 2")
+
+(defn rotations
+  "Returns a lazy seq of all rotations of a seq"
+  [x]
+  (if (seq x)
+    (map
+     (fn [n _]
+       (lazy-cat (drop n x) (take n x)))
+     (iterate inc 0) x)
+    (list nil)))
+
+(defn permutations
+  "Returns a lazy seq of all permutations of a seq"
+  [x]
+  (if (seq x)
+    (mapcat
+     (fn [[f & r]]
+       (map #(cons f %) (permutations r)))
+     (rotations x))
+    (list nil)))