lisp-random / partitions.lisp

;;;; partitions.lisp
;;;; Copyright (c) 2012 Robert Smith

(defun partitions (n &key size (minimum 1))
  "Compute the partitions of N. If SIZE is not provided, compute all
partitions. If SIZE is provided, only compute partitions of that
size. Values of the partition will be greater than or equal to
MINIMUM."
  (let ((result nil))
    (labels ((parts (n size i part)
               (if (= size 1)
                   ;; Base case, return the collected partition.
                   (push (cons n part) result)
                   
                   ;; General case: recurse, reducing the size.
                   (loop :for j :from i :to (floor n size)
                         :do (parts (- n j)
                                    (1- size)
                                    j
                                    (cons j part))))))
      (if (null size)
          ;; Compute all sizes.
          (loop :for k :from 1 :to n
                :do (parts n k minimum nil))
          
          ;; Compute a particular size.
          (parts n size minimum nil))
      
      ;; Return the collected result.
      result)))
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.