Implementation and tests for "combinations" function

2 files changed, 56 insertions, 0 deletions

diff --git a/combinations/combinations-test.scm b/combinations/combinations-test.scm
new file mode 100644
index 0000000..60f5fd1
--- /dev/null
+++ b/combinations/combinations-test.scm
@@ -0,0 +1,37 @@
+;; -*- compile-command: "guile -L . combinations-test.scm"; -*-
+(use-modules (srfi srfi-64)
+             (combinations))
+
+(test-begin "harness")
+
+
+(test-equal "zero combinations"
+  '(())
+  (combinations '(1 2 3 4 5) 0))
+
+(test-equal "single combinations"
+  '((1) (2) (3) (4) (5))
+  (combinations '(1 2 3 4 5) 1))
+
+(test-equal "double combinations"
+  '((1 2) (1 3) (1 4) (1 5)
+    (2 3) (2 4) (2 5)
+    (3 4) (3 5)
+    (4 5))
+  (combinations '(1 2 3 4 5) 2))
+
+(test-equal "triple combinations"
+  '((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5)
+    (2 3 4) (2 3 5) (2 4 5)
+    (3 4 5))
+  (combinations '(1 2 3 4 5) 3))
+
+(test-equal "quadruple combinations"
+  '((1 2 3 4) (1 2 3 5) (1 2 4 5) (1 3 4 5) (2 3 4 5))
+  (combinations '(1 2 3 4 5) 4))
+
+(test-equal "quintuple combinations"
+  '((1 2 3 4 5))
+  (combinations '(1 2 3 4 5) 5))
+
+(test-end "harness")
diff --git a/combinations/combinations.scm b/combinations/combinations.scm
new file mode 100644
index 0000000..8817176
--- /dev/null
+++ b/combinations/combinations.scm
@@ -0,0 +1,19 @@
+(define-module (combinations)
+  #:export (combinations))
+
+
+(define (combinations lst n)
+  "Return N length subsequences of elements from
+LST."
+  (if (or (null? lst) (zero? n))
+      (if (zero? n)'(()) '())
+      (let loop ((lst lst) (result '()))
+        (if (null? lst)
+            result
+            (let ((next-lst (cdr lst)))
+	      (loop next-lst
+                    (append result
+                            (map (lambda (combo)
+                                   (cons (car lst) combo))
+                                 (combinations next-lst
+					       (1- n))))))))))