Hi.
I now have a function which returns T or NIL when the list it gets
as parameter conforms to certain criteria.
I once saw as an example in FramerD's FDScript (example about
non-deterministic programming) a way of generating all possible combinations.
Something like:
(combi 'a 'b 'c)
-> (a b c)
-> (b a c)
-> (c b a)
... and so on.
Is there a fascility in Lisp to do this. If not, what is a good
starting point?
--
Thanks,
Mario <·····@delysid.org>
Homepage(s): http://delysid.org | http://piss.at/
Remember Darwin; building a better mousetrap merely results in smarter mice.
From: The Glauber
Subject: Re: All possible combinations out of some symbols
Date:
Message-ID: <8sfarc$lqs$1@nnrp1.deja.com>
In article <··············@home.delysid.org>,
Mario Lang <·····@home.delysid.org> wrote:
> Hi.
>
> I now have a function which returns T or NIL when the list it gets
> as parameter conforms to certain criteria.
>
> I once saw as an example in FramerD's FDScript (example about
> non-deterministic programming) a way of generating all possible combinations.
This is called permutations. I started a thread a couple of weeks ago. There
are several answers there:
http://www.deja.com/viewthread.xp?AN=674042477&group=comp.lang.lisp
The thread was called:
Q: tail-recursive procedure to generate all permutations of a list
--
Glauber Ribeiro
··········@my-deja.com http://www.myvehiclehistoryreport.com
"Opinions stated are my own and not representative of Experian"
Sent via Deja.com http://www.deja.com/
Before you buy.
From: Mario Lang
Subject: Re: All possible combinations out of some symbols (with unfixed length)
Date:
Message-ID: <87u2ac4qpj.fsf_-_@home.delysid.org>
The Glauber <··········@my-deja.com> writes:
> In article <··············@home.delysid.org>,
> Mario Lang <·····@home.delysid.org> wrote:
> > I now have a function which returns T or NIL when the list it gets
> > as parameter conforms to certain criteria.
> >
> > I once saw as an example in FramerD's FDScript (example about
> > non-deterministic programming) a way of generating all possible combinations.
>
> This is called permutations. I started a thread a couple of weeks ago. There
> are several answers there:
>
> http://www.deja.com/viewthread.xp?AN=674042477&group=comp.lang.lisp
Thanks for the pointer. This is very interesting, but I think I expressed myself
quite wrong.
I try to explain what I want once again:
I have a function, which returns T or NIL when the list it gets as parameter
conforms to certain criteria.
e.g.
(defun 10p (list)
"list is a list of numbers. Return T if the numbers add up to 10."
(eql (apply '+ list) 10))
NOw, I'd like to find all possible combinations which add up to ten.
e.g.
? (find-possibilities '(1 2 3 4 5 6 7 8 9 10) #'10p)
-> ((10)
(1 9) (2 8) (3 7) (4 6) (5 5) (6 4) (7 3) (8 2) (9 1)
(1 2 7) (1 3 6) ...)
Note that (1 9) and (9 1) are not the same. the order is different. A
mathematic approach would eliminate those possibilities. I dont want to do
this.
I played with the permutate-list functions in the thread you mentioned,
but couldn't find any way to alter it to do different length lists... hmm.
Is this way of doing permutation also called permutating, or is there a
different name for this?
BTW: This is not homework!
> --
> Glauber Ribeiro
> ··········@my-deja.com http://www.myvehiclehistoryreport.com
> "Opinions stated are my own and not representative of Experian"
--
CYa,
Mario <·····@delysid.org>
Homepage(s): http://delysid.org | http://piss.at/
The solution to a problem changes the nature of the problem.
-- Peer
From: ·················@p16.f41.n5045.z2.fidonet.org
Subject: Re: All possible combinations out of some symbols (with unfixed length)
Date:
Message-ID: <39eb974f@news.vtc.ru>
Mario Lang <·····@home.delysid.org> wrote:
>
> Note that (1 9) and (9 1) are not the same. the order is different. A
> mathematic approach would eliminate those possibilities. I dont want to do
> this.
>
> I played with the permutate-list functions in the thread you mentioned,
> but couldn't find any way to alter it to do different length lists... hmm.
>
I'm learning loops for now so I wrote that:
(defun vlpermut(list)
"var - length permutations"
(loop for digit in list
append (loop for tail in (vlpermut (remove digit list))
collect (append (list digit) tail))
collect (list digit)))
Seems it does what you want. You may try to understand it,
because I can't ;)
You may want to replace 'remove' to 'remove-if' for non-number and
non-symbol elements.
> Is this way of doing permutation also called permutating, or is there a
> different name for this?
Don't know about this.
> BTW: This is not homework!
c.l.l gives homeworks itself
From: Gareth McCaughan
Subject: Re: All possible combinations out of some symbols (with unfixed length)
Date:
Message-ID: <slrn8upnv1.je.Gareth.McCaughan@g.local>
Mario Lang wrote:
> I have a function, which returns T or NIL when the list it gets as parameter
> conforms to certain criteria.
> e.g.
>
> (defun 10p (list)
> "list is a list of numbers. Return T if the numbers add up to 10."
> (eql (apply '+ list) 10))
>
> NOw, I'd like to find all possible combinations which add up to ten.
> e.g.
> ? (find-possibilities '(1 2 3 4 5 6 7 8 9 10) #'10p)
> -> ((10)
> (1 9) (2 8) (3 7) (4 6) (5 5) (6 4) (7 3) (8 2) (9 1)
> (1 2 7) (1 3 6) ...)
You might like to look at the sections on Prolog in two classic
Lisp books: Paul Graham's "On Lisp" and Peter Norvig's "Paradigms
of Artificial Intelligence programming". What these are
discussing isn't exactly the same as what you ask for, but
it's similar enough that you'll probably find it interesting.
As for your specific problem, here's one way.
(defun find-possibilities (items predicate)
(let ((result nil))
(labels ((helper (remaining-items suffix)
(when (funcall predicate suffix)
(push suffix result))
(loop for tail on remaining-items do
(helper (nconc (ldiff remaining-items tail) (rest tail))
(cons (first tail) suffix)))))
(helper items '()))
result))
You could alternatively write the above code without PREDICATE
and then use REMOVE-IF-NOT, but that could really hurt when the
cases you actually want are a small fraction of the ones
possible. Or you could do that but use some sort of "lazy
list" instead of ordinary lists, but that is likely to be
expensive in time.
For some problems, you might find it helpful to alter the
code to allow PREDICATE to return a second value meaning
"no point looking any further".
(defun find-possibilities (items predicate)
(let ((result nil))
(labels ((helper (remaining-items suffix)
(multiple-value-bind (good cut) (funcall predicate suffix)
(when good (push suffix result))
(unless cut
(loop for tail on remaining-items do
(helper (nconc (ldiff remaining-items tail)
(rest tail))
(cons (first tail) suffix)))))))
(helper items '()))
result))
This speeds up your example by about a factor of 50000 on my
machine. :-)
--
Gareth McCaughan ················@pobox.com
sig under construc
From: Mario Lang
Subject: Re: All possible combinations out of some symbols (with unfixed length)
Date:
Message-ID: <87itqqsexv.fsf@home.delysid.org>
················@pobox.com (Gareth McCaughan) writes:
> Mario Lang wrote:
>
> > I have a function, which returns T or NIL when the list it gets as parameter
> > conforms to certain criteria.
> > e.g.
> >
> > (defun 10p (list)
> > "list is a list of numbers. Return T if the numbers add up to 10."
> > (eql (apply '+ list) 10))
> >
> > NOw, I'd like to find all possible combinations which add up to ten.
> > e.g.
> > ? (find-possibilities '(1 2 3 4 5 6 7 8 9 10) #'10p)
> > -> ((10)
> > (1 9) (2 8) (3 7) (4 6) (5 5) (6 4) (7 3) (8 2) (9 1)
> > (1 2 7) (1 3 6) ...)
>
> You might like to look at the sections on Prolog in two classic
> Lisp books: Paul Graham's "On Lisp" and Peter Norvig's "Paradigms
> of Artificial Intelligence programming". What these are
> discussing isn't exactly the same as what you ask for, but
> it's similar enough that you'll probably find it interesting.
Thanks, I'll try to get hold of those books.
I already abstracted my problem a bit more, and I now have a deeper
understanding of what I basicly want to do.
In essence, I want to count with symbols. Imagine if you
have '(0 1 2 3 4 5 6 7 8 9) as input, what I want to do is
basicly count from '(0) to e.g. '(9 9 9 9). This generates really ALL
possibilities. I'll post what I come up with when I have something...
Your function basicly does what I want. Here is my test with it:
> (find-possibilities '(1 2 3 4 5) #'(lambda (list) (eql (apply #'+ list) 5)))
((5) (1 4) (2 3) (3 2) (4 1))
except that the list should also contain:
((2 2 1) (2 1 2) (1 2 2) (1 1 1 2) (1 1 2 1) ...)
Thanks for the inspiration.
>
> As for your specific problem, here's one way.
>
> (defun find-possibilities (items predicate)
> (let ((result nil))
> (labels ((helper (remaining-items suffix)
> (when (funcall predicate suffix)
> (push suffix result))
> (loop for tail on remaining-items do
> (helper (nconc (ldiff remaining-items tail) (rest tail))
> (cons (first tail) suffix)))))
> (helper items '()))
> result))
>
> You could alternatively write the above code without PREDICATE
> and then use REMOVE-IF-NOT, but that could really hurt when the
> cases you actually want are a small fraction of the ones
> possible. Or you could do that but use some sort of "lazy
> list" instead of ordinary lists, but that is likely to be
> expensive in time.
>
> For some problems, you might find it helpful to alter the
> code to allow PREDICATE to return a second value meaning
> "no point looking any further".
>
> (defun find-possibilities (items predicate)
> (let ((result nil))
> (labels ((helper (remaining-items suffix)
> (multiple-value-bind (good cut) (funcall predicate suffix)
> (when good (push suffix result))
> (unless cut
> (loop for tail on remaining-items do
> (helper (nconc (ldiff remaining-items tail)
> (rest tail))
> (cons (first tail) suffix)))))))
> (helper items '()))
> result))
>
> This speeds up your example by about a factor of 50000 on my
> machine. :-)
>
> --
> Gareth McCaughan ················@pobox.com
> sig under construc
--
CYa,
Mario <·····@delysid.org>
Homepage(s): http://delysid.org | http://piss.at/
CChheecckk yyoouurr dduupplleexx sswwiittcchh..
From: Gareth McCaughan
Subject: Re: All possible combinations out of some symbols (with unfixed length)
Date:
Message-ID: <slrn8us52r.ud.Gareth.McCaughan@g.local>
Mario Lang wrote:
> In essence, I want to count with symbols. Imagine if you
> have '(0 1 2 3 4 5 6 7 8 9) as input, what I want to do is
> basicly count from '(0) to e.g. '(9 9 9 9). This generates really ALL
> possibilities. I'll post what I come up with when I have something...
>
> Your function basicly does what I want. Here is my test with it:
> > (find-possibilities '(1 2 3 4 5) #'(lambda (list) (eql (apply #'+ list) 5)))
> ((5) (1 4) (2 3) (3 2) (4 1))
>
> except that the list should also contain:
> ((2 2 1) (2 1 2) (1 2 2) (1 1 1 2) (1 1 2 1) ...)
Oh yes. I didn't notice you had (5 5) in your list of answers you wanted.
That actually makes the code much easier. (Although it also means that
you *must* provide some sort of "no need to explore further" test,
because otherwise there are infinitely many lists to test.) The
following corresponds to the revised version in my earlier article;
PREDICATE should return two values.
(defun find-possibilities (items predicate)
(let ((result nil))
(labels ((helper (suffix)
(multiple-value-bind (good cut) (funcall predicate suffix)
(when good (push suffix result))
(unless cut
(dolist (item items)
(helper (cons item suffix)))) )))
(helper '()))
result))
Something I forgot to say before: You can greatly reduce the
amount of consing (i.e., memory allocation) by using vectors
instead of lists. This is less important for the new version
of the code than the old (because the LDIFF in the old version
always conses), but it could still be significant.
--
Gareth McCaughan ················@pobox.com
sig under construc
From: Thomas A. Russ
Subject: Re: All possible combinations out of some symbols
Date:
Message-ID: <ymid7h04rox.fsf@sevak.isi.edu>
Mario Lang <·····@home.delysid.org> writes:
> I once saw as an example in FramerD's FDScript (example about
> non-deterministic programming) a way of generating all possible combinations.
> Something like:
Actually, it looks like you are looking for permutations, not
combinations.
> (combi 'a 'b 'c)
> -> (a b c)
> -> (b a c)
> -> (c b a)
> ... and so on.
>
> Is there a fascility in Lisp to do this. If not, what is a good
> starting point?
dejanews.com and look for the recent thread on permutations in this
newsgroup.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu