Given a list (really a set) of N elements, how do I get all
subdivisions to M lists of length K (M*K==N)? (I wish this was a
homework problem.) The ordering within the sublists doesn't matter,
if it did, it would be easy to take all permutations of the original
list and return them subdivided. I must be missing something fairly
simple here; it has obviously been too long since I took classes in
combinatorics...
--
Ola Rinta-Koski ···@cyberell.com
Cyberell Oy +358 41 467 2502
Rauhankatu 8 C, FIN-00170 Helsinki, FINLAND www.cyberell.com
perhaps
(defun combinatoric (list n)
(if (<= n 1)
(mapcar 'list list)
(loop for sublist = list then (rest sublist)
until (null sublist)
if (>= (length sublist) n)
append (mapcar #'(lambda (tail)
(cons (car sublist) tail))
(combinatoric (rest sublist) (1- n))))))
is sufficient? You did say this wasn't a homework...
Ola Rinta-Koski wrote:
>
> Given a list (really a set) of N elements, how do I get all
> subdivisions to M lists of length K (M*K==N)? (I wish this was a
> homework problem.) The ordering within the sublists doesn't matter,
> if it did, it would be easy to take all permutations of the original
> list and return them subdivided. I must be missing something fairly
> simple here; it has obviously been too long since I took classes in
> combinatorics...
> --
> Ola Rinta-Koski ···@cyberell.com
> Cyberell Oy +358 41 467 2502
> Rauhankatu 8 C, FIN-00170 Helsinki, FINLAND www.cyberell.com
Ola Rinta-Koski wrote:
> Given a list (really a set) of N elements, how do I get all
> subdivisions to M lists of length K (M*K==N)? (I wish this was a
> homework problem.) The ordering within the sublists doesn't matter,
> if it did, it would be easy to take all permutations of the original
> list and return them subdivided. I must be missing something fairly
> simple here; it has obviously been too long since I took classes in
> combinatorics...
(defun splittings (list sublist-length)
"Return a list containing all partitions of LIST into
sublists all of length SUBLIST-LENGTH, where the order
of elements within a sublist is not important but the
order in which sublists occur is. The caller guarantees
that the length of LIST is a multiple of SUBLIST-LENGTH."
;; 1. If the list is empty, there's only one possibility.
(when (null list)
(return-from splittings (list ())))
;; 2. Otherwise, enumerate single sublists (subsets, really)
;; and find all answers starting with each of them.
(loop for sublist in (ordered-sublists list sublist-length)
nconc (prepend-to-each sublist
(splittings (set-difference list sublist)
sublist-length))))
(defun ordered-sublists (list sublist-length)
"Return a list containing each sublist of LIST
having length SUBLIST-LENGTH and elements in the same
order as in LIST.
This is a very inefficient implementation. It's possible to
do much better by being more sophisticated, or to do somewhat
better just by memoizing."
(when (> sublist-length (length list))
(return-from ordered-sublists nil))
(when (zerop sublist-length)
(return-from ordered-sublists (list nil)))
(nconc (ordered-sublists (rest list) sublist-length)
(prepend-to-each (first list)
(ordered-sublists (rest list) (1- sublist-length)))))
(defun prepend-to-each (item list)
"Return a list containing each element of LIST, each with
ITEM consed onto the front. LIST must be a list of lists."
(mapcar (lambda (x) (cons item x)) list))
You could make the whole thing more efficient by having ORDERED-SUBLISTS
actually return not just the sublists but the <sublist, remaining-elements>
pairs.
Timings for the above code using CMUCL on my machine (Athlon/1G
running FreeBSD):
length of list sublist-length number of splittings seconds
9 3 1680 0.01
12 4 34650 1.53
12 3 369600 14.85
In each of those cases, the majority of time was spent in GC.
This suggests that one could do better. :-)
--
Gareth McCaughan ················@pobox.com
.sig under construc
················@pobox.com (Gareth McCaughan) writes:
> Ola Rinta-Koski wrote:
> > Given a list (really a set) of N elements, how do I get all
> > subdivisions to M lists of length K (M*K==N)?
> (defun splittings (list sublist-length)
(...)
It would seem to do the trick, thanks (thanks to all the others who
replied either in public or in private as well).
As an aside, the application is being developed to be used as a
compositional aid; the composer (Daniel Schell) had this to say
about Lisp:
LISP reminds me of the raaga. It seems obscure to the beginner,
but you feel that it is a best survivor of an ancestral tradition
of logicians. So although you do not understand it at first, you
feel unconsciously that you have to respect it...
--
Ola Rinta-Koski ···@cyberell.com
Cyberell Oy +358 41 467 2502
Rauhankatu 8 C, FIN-00170 Helsinki, FINLAND www.cyberell.com