I'm new to lisp, using GNU Clisp.
I have a problem when I do some Lisp programming training.
For example, for the list (a (b1 b2) c (d1 d2) (e1 e2 e3) f), I need a
function to return all the possible combinations like:
((a b1 c d1 e1 f)
(a b1 c d1 e2 f)
(a b1 c d1 e3 f)
(a b1 c d2 e1 f)
(a b1 c d2 e2 f)
(a b1 c d2 e3 f)
(a b2 c d1 e1 f)
(a b2 c d1 e2 f)
(a b2 c d1 e3 f)
(a b2 c d2 e1 f)
(a b2 c d2 e2 f)
(a b2 c d2 e3 f))
My tries trended to be unsuccessful. It's not homework. Can highhand
help?
best regards,
keyboard
"keyboard" <·············@thomson.net> writes:
> I'm new to lisp, using GNU Clisp.
>
> I have a problem when I do some Lisp programming training.
>
> For example, for the list (a (b1 b2) c (d1 d2) (e1 e2 e3) f), I need a
> function to return all the possible combinations like:
> ((a b1 c d1 e1 f)
> (a b1 c d1 e2 f)
> (a b1 c d1 e3 f)
> (a b1 c d2 e1 f)
> (a b1 c d2 e2 f)
> (a b1 c d2 e3 f)
> (a b2 c d1 e1 f)
> (a b2 c d1 e2 f)
> (a b2 c d1 e3 f)
> (a b2 c d2 e1 f)
> (a b2 c d2 e2 f)
> (a b2 c d2 e3 f))
>
> My tries trended to be unsuccessful. It's not homework. Can highhand
> help?
I would normalize first the list:
(a (b1 b2) c (d1 d2) (e1 e2 e3) f)
--> ((a) (b1 b2) (c) (d1 d2) (e1 e2 e3) (f))
Then you can develop easily a recursive algorithm:
The base case is:
- the combinations of () are (())
The recursive formula will be of the form:
- when you have a list
(combinations list) = (f (first list) (combinations (rest list)))
You need to write the function f.
For example, when list = ((a b c))
(first list) = (a b c)
(rest list) = ()
From the base case:
(combinations (rest list)) = (())
So you need to call: (f '(a b c) '(()))
and obtain: ((a) (b) (c))
Take as second example: list = ((a b c) (1 2 3))
and the definition of f should become obvious.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Our users will know fear and cower before our software! Ship it!
Ship it and let them flee like the dogs they are!"
Thank you very much, Pascal.
In the meantime, I found you older post about this problem. The
solusion is good. It took me some time to understand.
best regards,
keyboard
Pascal Bourguignon schrieb:
> "keyboard" <·············@thomson.net> writes:
> > I'm new to lisp, using GNU Clisp.
> >
> > I have a problem when I do some Lisp programming training.
> >
> > For example, for the list (a (b1 b2) c (d1 d2) (e1 e2 e3) f), I need a
> > function to return all the possible combinations like:
> > ((a b1 c d1 e1 f)
> > (a b1 c d1 e2 f)
> > (a b1 c d1 e3 f)
> > (a b1 c d2 e1 f)
> > (a b1 c d2 e2 f)
> > (a b1 c d2 e3 f)
> > (a b2 c d1 e1 f)
> > (a b2 c d1 e2 f)
> > (a b2 c d1 e3 f)
> > (a b2 c d2 e1 f)
> > (a b2 c d2 e2 f)
> > (a b2 c d2 e3 f))
> >
> > My tries trended to be unsuccessful. It's not homework. Can highhand
> > help?
>
> I would normalize first the list:
>
> (a (b1 b2) c (d1 d2) (e1 e2 e3) f)
> --> ((a) (b1 b2) (c) (d1 d2) (e1 e2 e3) (f))
>
>
> Then you can develop easily a recursive algorithm:
>
> The base case is:
> - the combinations of () are (())
>
> The recursive formula will be of the form:
>
> - when you have a list
> (combinations list) = (f (first list) (combinations (rest list)))
>
> You need to write the function f.
>
> For example, when list = ((a b c))
> (first list) = (a b c)
> (rest list) = ()
> From the base case:
> (combinations (rest list)) = (())
>
> So you need to call: (f '(a b c) '(()))
> and obtain: ((a) (b) (c))
>
>
> Take as second example: list = ((a b c) (1 2 3))
> and the definition of f should become obvious.
>
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> "Our users will know fear and cower before our software! Ship it!
> Ship it and let them flee like the dogs they are!"
> > "keyboard" <·············@thomson.net> writes:
> > > I'm new to lisp, using GNU Clisp.
> > >
> > > I have a problem when I do some Lisp programming training.
> > >
> > > For example, for the list (a (b1 b2) c (d1 d2) (e1 e2 e3) f), I need a
> > > function to return all the possible combinations like:
> > > ((a b1 c d1 e1 f)
> > > (a b1 c d1 e2 f)
> > > (a b1 c d1 e3 f)
> > > (a b1 c d2 e1 f)
> > > (a b1 c d2 e2 f)
> > > (a b1 c d2 e3 f)
> > > (a b2 c d1 e1 f)
> > > (a b2 c d1 e2 f)
> > > (a b2 c d1 e3 f)
> > > (a b2 c d2 e1 f)
> > > (a b2 c d2 e2 f)
> > > (a b2 c d2 e3 f))
> > >
> > > My tries trended to be unsuccessful. It's not homework. Can highhand
> > > help?
I didn't reply to the original post because Pascal had
already answered and his answer was perfect and left nothing
to add.
Well, perhaps there is a little to add. There is an
alternative approach that is sometimes useful. The core idea
is the Cartesian Product. It is easy enough to write a
Cartesian Product for two arguments:
(defun cartesian-product (r s)
(let (product)
(dolist (x r)
(dolist (y s)
(push (cons x y)
product)))
(nreverse product)))
but how do you generalise the code for N arguments? On way
is to use REDUCE
(defun combinations (list)
(reduce #'cartesian-product
list
:from-end t
:initial-value '(())))
(combinations '((a) (b1 b2) (c) (d1 d2) (e1 e2 e3) (f))) =>
((A B1 C D1 E1 F) (A B1 C D1 E2 F) (A B1 C D1 E3 F) (A B1 C D2 E1 F)
(A B1 C D2 E2 F) (A B1 C D2 E3 F) (A B2 C D1 E1 F) (A B2 C D1 E2 F)
(A B2 C D1 E3 F) (A B2 C D2 E1 F) (A B2 C D2 E2 F) (A B2 C D2 E3 F))
Some people dislike REDUCE
http://lambda-the-ultimate.org/node/view/587
I think that the key to understanding it is to define a
formal function
(defun formal-function (x y)
(list 'f x y))
Then it is easy to play with, to see what it does
(reduce #'formal-function '(1 2 3) :initial-value 0)
=> (F (F (F 0 1) 2) 3)
(reduce #'formal-function '(1 2 3) :initial-value 0 :from-end t)
=> (F 1 (F 2 (F 3 0)))
Alan Crowe
Edinburgh
Scotland
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> I think that the key to understanding it is to define a
> formal function
>
> (defun formal-function (x y)
> (list 'f x y))
Nice abstraction :-)
> Then it is easy to play with, to see what it does
>
> (reduce #'formal-function '(1 2 3) :initial-value 0)
> => (F (F (F 0 1) 2) 3)
>
> (reduce #'formal-function '(1 2 3) :initial-value 0 :from-end t)
> => (F 1 (F 2 (F 3 0)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
The mighty hunter
Returns with gifts of plump birds,
Your foot just squashed one.