Hi,
Can anybody help with implementation of genarator for combinations
without repetitions in Lisp? I've managed to write one in Haskel using
list comprehensions, but I have problems implementing it in Lisp.
(combi 2 '(1 2 3)) => ((1 2) (13) (2 3))
(combi 3 '(1 2 3 4)) => ((1 2 3) (1 2 4) (1 3 4) (2 3 4))
etc...
thanks for any thoughts
regards
Krzys
On Apr 2, 10:55 am, ················@googlemail.com wrote:
> Hi,
>
> Can anybody help with implementation of genarator for combinations
> without repetitions in Lisp? I've managed to write one in Haskel using
> list comprehensions, but I have problems implementing it in Lisp.
>
> (combi 2 '(1 2 3)) => ((1 2) (13) (2 3))
> (combi 3 '(1 2 3 4)) => ((1 2 3) (1 2 4) (1 3 4) (2 3 4))
>
> etc...
>
> thanks for any thoughts
> regards
> Krzys
Here's a cut-and-paste of an old post about this subject where I asked
a similar question.
On Jan 24 2006, 8:28 pm, David Sletten <····@slytobias.com> wrote:
> Andrew Baine wrote:
> > Below is a function list-combinations that takes a list lst an an
> > integer n and returns a list of all n-element combinations of lst. The
> > function uses divide and conquer recursion, dividing all n-element
> > combinations into those that contain the first element of lst and those
> > that do not.
>
> > ;;;; returns a list of all n-element combinations
> > ;;;; of the list lst
> > (defun list-combinations (lst n)
> > (cond
> > ((> n (length lst)) nil)
> > ((< n 1) nil)
> > ((< n 2) (mapcar #'list lst))
> > (t (let ((big-list (list-combinations (cdr lst) n))
> > (small-list (list-combinations (cdr lst) (1- n))))
> > (append (mapcar (lambda (e) (cons (car lst) e)) small-list)
> > big-list)))))
>
> As an alternative recursive version I think this is more idiomatic Lisp:
> (defun combinations (l r)
> (cond ((zerop r) (list '()))
> ((null l) '())
> (t (spread-elt (first l)
> (combinations (rest l) (1- r))
> (combinations (rest l) r)))) )
>
> ;;;
> ;;; Distribute ELT across each sublist in PARTIAL accumulating them in
> ;;; (possibly pre-existing) RESULT.
> ;;;
> ;;; (spread-elt 'a '((b c) (c b)) '()) => ((A B C) (A C B))
> ;;;
> ;;; (spread-elt 'a '((b c) (c b)) '((b c a) (b a c) (c b a) (c a b))) =>
> ;;; ((A B C) (A C B) (B C A) (B A C) (C B A) (C A B))
> ;;;
> (defun spread-elt (elt partial result)
> (cond ((null partial) result)
> (t (cons (cons elt (first partial))
> (spread-elt elt (rest partial) result)))) )
>
> Notice how we can avoid using LENGTH and APPEND. Your version appears to
> cons 30-50% more than this one.
>
> Aloha,
> David Sletten
From: Christian Haselbach
Subject: Re: Back to the basics - combinations :)
Date:
Message-ID: <eurm9u$6hu$1@online.de>
················@googlemail.com wrote:
> Can anybody help with implementation of genarator for combinations
> without repetitions in Lisp? I've managed to write one in Haskel using
> list comprehensions, but I have problems implementing it in Lisp.
If you had posted your Haskel solution, one could have tried to give you
a direct translation.
Here is a solution for a quite similar problem, where the order of the
drawings matter:
(defun combi* (n l)
(if (zerop n)
'(nil)
(mapcan (lambda (x) (mapcar (lambda (k) (cons x k))
(combi (1- n) (remove x l))))
l)))
The set of all combinations of l without repetition of length 0 is the
set that contains the empty list.
The set of all combinations of l without repetition of length n is the
set that is the union of all combinations of l without x without
repetition of length n-1 for for all x in l.
The above is basically a direct translation into lisp.
The solution (well, one solution) for your problem is quite similar.
(defun combi (n l)
(if (zerop n)
'(nil)
(mapcon (lambda (j) (mapcar (lambda (k) (cons (car j) k))
(combi (1- n) (cdr j))))
l)))
Of course, this is not the best performing solution. For starters, it is
not tail-recursive.
Regards,
Christian
On 2007-04-02, Christian Haselbach <······@muon.de> wrote:
> ················@googlemail.com wrote:
>> Can anybody help with implementation of genarator for combinations
>> without repetitions in Lisp? I've managed to write one in Haskel using
>> list comprehensions, but I have problems implementing it in Lisp.
>
> The solution (well, one solution) for your problem is quite similar.
>
> (defun combi (n l)
> (if (zerop n)
> '(nil)
> (mapcon (lambda (j) (mapcar (lambda (k) (cons (car j) k))
> (combi (1- n) (cdr j))))
> l)))
>
> Of course, this is not the best performing solution. For starters, it is
> not tail-recursive.
>
> Regards,
> Christian
I took a crack a tail-recursive solution, but it's slower, not faster, than my
non-tail-recursive solution.
Here's my non-tail-recursive version:
(defun set-choose-k (set k &optional (comp-set nil))
"returns a list of the k element subsets of set with comp-set
prepended to each in reverse"
(cond
((zerop k) (list (reverse comp-set)))
((null set) nil)
(t (append
(set-choose-k (cdr set) (1- k) (cons (car set) comp-set))
(set-choose-k (cdr set) k comp-set)))))
Note (set-choose-k set k) <=> (combi k set)
It's analogous to this definition of the binomial coefficient:
(defun n-choose-k (n k)
"returns the number of k element subsets of an n element set"
(cond
((zerop k) 1)
((zerop n) 0)
(t (+
(n-choose-k (1- n) (1- k))
(n-choose-k (1- n) k)))))
Here's my tail-recursive version:
(defun set-choose-k-tail-rec (set k)
(sck (list (list k set nil)) nil))
(defun sck (partials accum)
"partials is a list of elements of the form (number set comp-set)
where comp-set and set are disjoint lists. For each (j set comp-set)
in partials, append to accum all sets that are the union of comp-set
and a j element subset of set."
(when (not partials) (return-from sck accum))
(loop for (j set comp-set) in partials
when (zerop j) collect comp-set into naccum
else when set
collect (list j (cdr set) comp-set) into npartials
and
collect (list (1- j) (cdr set) (cons (car set) comp-set)) into npartials
finally (setf partials npartials accum (append naccum accum)))
(sck partials accum))
Here are the tests I ran:
(defparameter *set* (loop for i from 1 to 20 collecting i))
(time (length (set-choose-k *set* 10)))
(time (length (set-choose-k-tail-rec *set* 10)))
(time (length (combi 10 *set*)))
How do you get better performance?
Win