Composition of n into k parts
13th September 2015
For a recent project I wanted to split a string of characters into every possible set of four non-empty substrings. For example, if the string was "abcdef" this would give:
"abc" "d" "e" "f" "ab" "c" "de" "f" "ab" "c" "d" "ef" "ab" "cd" "e" "f" "a" "b" "cde" "f" "a" "b" "cd" "ef" "a" "b" "c" "def" "a" "bc" "de" "f" "a" "bc" "d" "ef" "a" "bcd" "e" "f"
For an arbitrary string of n characters divided into k parts, how many are there? Also, I wanted to write a Lisp program to generate all the strings.
Calculating the number of elements
First let's consider a variant of the problem in which you are allowed to have zero items in each part. How many compositions are there? Let's take the example of dividing 6 items into 4 parts.
This is equivalent to the problem of arranging 6 balls in a row of 9 slots, each of which can contain at most one ball. An empty slot can be considered as the dividing line between one part and the next.
For example, here's one arrangement of balls:
O _ O O O _ O _ O
and the equivalent strings:
"a" "bcd" "e" "f"
Clearly, you can do this in:
C(n+k-1, n) ways.
To solve the original problem, with at least one item in each part, solve it for (n-k) parts and add 1 to each part. Therefore, in this case you can do it in:
C(n-1, n-k) ways.
For the original example using the string "abcdef" n=6 and k-4, and this gives the number of compositions as 10.
A Lisp implementation
The most intuitive way of implementing (compositions n k) is:
- If there's only one part, this part contains n items.
- Otherwise, put i items in the first part, where i can be from 0 to n, and for each of these options put the remaining items in the remaining parts according to (compositions (- n i) ( 1- k)).
Here's the recursive definition in Lisp:
(defun compositions (n k)
"Composition of n into k parts."
(cond
((= k 1) (list (list n)))
(t (let (result)
(dotimes (i (1+ n) result)
(map nil #'(lambda (item) (push (cons i item) result))
(compositions (- n i) (1- k))))))))
For example, the result corresponding to the above strings is:
> (compositions 2 4) ((2 0 0 0) (1 0 1 0) (1 0 0 1) (1 1 0 0) (0 0 2 0) (0 0 1 1) (0 0 0 2) (0 1 1 0) (0 1 0 1) (0 2 0 0))
To generate the strings we can use:
(defun compositions* (string k)
"Composition of string into k parts, each contains at least one character."
(map 'list
#'(lambda (l)
(let ((start 0))
(map 'list
#'(lambda (n) (subseq string start (incf start (1+ n)))) l)))
(compositions (- (length string) k) k)))
This excludes zero-length strings by calculating:
(compositions (- n k) k)
and adding 1 to each value. For example:
> (compositions* "abcdef" 4)
(("abc" "d" "e" "f") ("ab" "c" "de" "f") ("ab" "c" "d" "ef") ("ab" "cd" "e" "f")
("a" "b" "cde" "f") ("a" "b" "cd" "ef") ("a" "b" "c" "def") ("a" "bc" "de" "f")
("a" "bc" "d" "ef") ("a" "bcd" "e" "f"))
Non-recursive version
I subsequently developed a more efficient non-recursive version as a macro [1]; this gives the compositions in an array r:
(defmacro with-compositions ((r n k) &body body)
"Composition of n into k parts."
(let ((term (gensym))
(h (gensym)))
`(let ((,r (make-array ,k :initial-element 0))
(,term ,n) ,h)
(setf (aref ,r 0) ,n)
(loop
,@body
(when (= (aref ,r (1- ,k)) ,n) (return))
(when (> ,term 1) (setq ,h -1))
(incf ,h)
(setq ,term (aref ,r ,h))
(setf (aref ,r ,h) 0)
(setf (aref ,r 0) (1- ,term))
(incf (aref ,r (1+ ,h)))))))
For example:
> (with-compositions (r 2 4) (format t "~a " r)) #(2 0 0 0) #(1 1 0 0) #(0 2 0 0) #(1 0 1 0) #(0 1 1 0) #(0 0 2 0) #(1 0 0 1) #(0 1 0 1) #(0 0 1 1) #(0 0 0 2)
- ^ Based on an algorithm from Nijenhuis, Albert and Herbert S. Wilf (1978), Combinatorial Algorithms, Academic Press, 1978.
blog comments powered by Disqus