Hi.
I now crafted my first litttle bit more complex lisp fucntion together.
My aim is to get all possible combinations out of a list of symbols.
After thinking alot about the problem, I came to the conclusion
that this is in essence just counting. Here is what I got so far:
(defun symcount-2n (syms)
"Returns list with max length of 2"
(loop for i in (cons nil syms)
append (loop for j in syms
collect (if (null i) (list j) (cons i (list j))))))
And here is a example:
? (symcount-2n '(a b c))
((A) (B) (C)
(A A) (A B) (A C)
(B A) (B B) (B C)
(C A) (C B) (C C))
Does anyone have an idea how I could bring a variable
n into the whole thing so that I could set the maximum length of the
returned list?
This is currently kinda hardcoded :).
--
CYa,
Mario <·····@delysid.org>
Homepage(s): http://delysid.org | http://piss.at/
Mario Lang <·····@home.delysid.org> writes:
> (defun symcount-2n (syms)
> "Returns list with max length of 2"
> (loop for i in (cons nil syms)
> append (loop for j in syms
> collect (if (null i) (list j) (cons i (list j))))))
>
> And here is a example:
> ? (symcount-2n '(a b c))
> ((A) (B) (C)
> (A A) (A B) (A C)
> (B A) (B B) (B C)
> (C A) (C B) (C C))
>
> Does anyone have an idea how I could bring a variable
> n into the whole thing so that I could set the maximum length of the
> returned list?
Of course I mean the maximum length of the sublists.
--
CYa,
Mario <·····@delysid.org>
Homepage(s): http://delysid.org | http://piss.at/
All language designers are arrogant. Goes with the territory... :-)
-- Larry Wall in <······················@netlabs.com
Mario Lang <·····@home.delysid.org> writes:
> (defun symcount-2n (syms)
> "Returns list with max length of 2"
> (loop for i in (cons nil syms)
> append (loop for j in syms
> collect (if (null i) (list j) (cons i (list j))))))
...
> Does anyone have an idea how I could bring a variable
> n into the whole thing so that I could set the maximum length of the
> returned list?
> This is currently kinda hardcoded :).
I would suggest writing a function called e.g. CONS-ALL, that takes a
list of symbols and a list of lists, and returns a list of all
possible CONSes between the two of them. (Fairly like the one you have
but without the CONS NIL/IF NULL trick)
Now, all combinations of length zero is (()).
From this we can construct all combinations of length one as
(setf current-list (cons-all syms current-list))
From this we can construct all combinations of length two as
(setf current-list (cons-all syms current-list))
... and so on.
Then write a loop up to n which does the above and collects the
results into a long long list. Presto.
(You could at this point insert the definition of CONS-ALL into the
other function to create one long function doing the whole thing, but
I wouldn't recommend it)
Stig Hemmer,
Jack of a Few Trades.
I wrote:
> > (defun symcount-2n (syms)
> > "Returns list with max length of 2"
> > (loop for i in (cons nil syms)
> > append (loop for j in syms
> > collect (if (null i) (list j) (cons i (list j))))))
> ...
> > Does anyone have an idea how I could bring a variable
> > n into the whole thing so that I could set the maximum length of the
> > returned list?
> > This is currently kinda hardcoded :).
Stig Hemmer <····@pvv.ntnu.no> answered:
> I would suggest writing a function called e.g. CONS-ALL, that takes a
> list of symbols and a list of lists, and returns a list of all
> possible CONSes between the two of them. (Fairly like the one you have
> but without the CONS NIL/IF NULL trick)
Wow. I had to read the sentence twice, but after I got your point, I was really
enlightened.
Here is what I finally came up with:
(defun find-possibilities (symlist max-lol-length predicate)
"Finds all possible lists out of symlist symbols which pass predicate test."
(let ((cur-list ()))
(loop for i below max-lol-length
append (loop for res in (setf cur-list (cons-all symlist cur-list))
when (funcall predicate res)
collect res))))
(defun cons-all (syms list-of-lists)
"Returns all possible conses of
symbols in syms with lists in list-of-lists."
(loop for i in syms
as res = (if (null list-of-lists)
(list (list i))
(loop for j in list-of-lists
collect (cons i j)))
append res))
(defun mytest (list)
"An example preedicate for find-possibilities.
Note that the predicate doesn't necessarily have to deal with numbers.
Symbols, strings or whatever are just fine."
(eql (apply #'+ list) 5))
? (find-possibilities '(1 2 3 4 5) 3 #'mytest)
((5) (1 4) (2 3) (3 2) (4 1) (1 1 3) (1 2 2) (1 3 1) (2 1 2) (2 2 1) (3 1 1))
I have to thank all people in this group for patiently trying
to give me pointers into the right direction although
I probably expressed my goals quite cryptically.
This is my Lisp-learning program, written while reading Successful Lisp
(which is a great book BTW).
It is IMHO quite generic, and can be used to find alot of things.
Perhaps the predicate-test could be optimized. My first version had
the predicate test in cons-all. But when I finished everything I realized
that this CAN'T work, because cons-all has to return ALL lists to make the
whole thing work. So I had to insert another loop, which
is a real performance lose. Memory consumtion is extreme, example:
? (time (length (find-possibilities '(0 1 2 3 4 5 6 7) 7 #'mytest)))
Real time: 24.044622 sec.
Run time: 23.57 sec.
Space: 57536640 Bytes
GC: 17, GC time: 13.01 sec.
924
Once again, thanks for your patients. I knew that Lisp is a nice
language for doing such things, but I couldn't imagine
that it is so efficient.
> Now, all combinations of length zero is (()).
^^^^
Hmm, perhaps I just found one optimization myself. The
(if (null list-of-lists)) isn't really necessary...
> Then write a loop up to n which does the above and collects the
> results into a long long list. Presto.
Yes.
> (You could at this point insert the definition of CONS-ALL into the
> other function to create one long function doing the whole thing, but
> I wouldn't recommend it)
Hmmm, what would that mean in terms of performance?
I think the interpreter optimizes such things? OK, perhaps it isn't
as interesting as memory-useage is for this job.
E.g. doing (find-possibilities '(1 2 3 4 5 6 7) 8 #'mytest)
is nearly impossible on my machine (128MB RAM with 70MB Swap).
I could live with it if it took several days or weeks, but the memory
consumtion is a real issue.
>
> Stig Hemmer,
> Jack of a Few Trades.
>
--
CYa,
Mario <·····@delysid.org>
Homepage(s): http://delysid.org | http://piss.at/
Mario Lang wrote:
> My aim is to get all possible combinations out of a list of symbols.
> (defun symcount-2n (syms)
> "Returns list with max length of 2"
> (loop for i in (cons nil syms)
> append (loop for j in syms
> collect (if (null i) (list j) (cons i (list j))))))
>
> And here is a example:
> ? (symcount-2n '(a b c))
> ((A) (B) (C)
> (A A) (A B) (A C)
> (B A) (B B) (B C)
> (C A) (C B) (C C)
> Does anyone have an idea how I could bring a variable
> n into the whole thing so that I could set the maximum length of the
> returned list?
Here's my try:
(defun combinations (n l)
"Return all lists made from elements of l, of length at most n."
(loop repeat n
as combinations = (mapcar #'list l)
then (loop for x in l
append (loop for c in combinations collect (cons x c)))
append combinations))
However, I suggest using a function that outputs all combinations of
length
exactly n. It would take as input the list of symbols to combine, and
the list of all
combinations of length n-1.
> I came to the conclusion that this is in essence just counting.
Hmm, there are more combinations than numbers.
In the example cited above, if (A) maps to zero, so does (A A).
More generally, the algo produces "numbers" with n-1 leading zeros.
Michael
--
Mario Lang wrote:
> I now crafted my first litttle bit more complex lisp fucntion together.
> My aim is to get all possible combinations out of a list of symbols.
> After thinking alot about the problem, I came to the conclusion
> that this is in essence just counting. Here is what I got so far:
>
> (defun symcount-2n (syms)
> "Returns list with max length of 2"
> (loop for i in (cons nil syms)
> append (loop for j in syms
> collect (if (null i) (list j) (cons i (list j))))))
>
> And here is a example:
> ? (symcount-2n '(a b c))
> ((A) (B) (C)
> (A A) (A B) (A C)
> (B A) (B B) (B C)
> (C A) (C B) (C C))
You missed out the empty list. :-) (If you think having
missed out the empty list is a feature, then I advise you
to change your sense of elegance so that it isn't. Really.)
> Does anyone have an idea how I could bring a variable
> n into the whole thing so that I could set the maximum length of the
> sublists? [<== corrected --gjm]
> This is currently kinda hardcoded :).
Here's one way to think about it.
You've got a bunch of items, and you already know all the
sublists of length <= n-1. You can get all the sublists
of length <= n by taking all the ones of length <= n-1
and, for each, adding on all the items in your bunch.
This gives you all but the empty list, so throw that in
too.
It's not too hard to turn this into a simple recursive
function. My currently-preferred version is 4 lines long,
but you'll learn faster if you work out how to do it
for yourself. (Don't worry if it takes you more than
4 lines!)
--
Gareth McCaughan ················@pobox.com
sig under construc
················@pobox.com (Gareth McCaughan) writes:
> Mario Lang wrote:
>
> > And here is a example:
> > ? (symcount-2n '(a b c))
> > ((A) (B) (C)
> > (A A) (A B) (A C)
> > (B A) (B B) (B C)
> > (C A) (C B) (C C))
>
> You missed out the empty list. :-) (If you think having
> missed out the empty list is a feature, then I advise you
> to change your sense of elegance so that it isn't. Really.)
Hmm, I can see your point, although the final version uses
a predicate to reduce the length of the final list-of-lists, and this would
probably only add overhead for the predication function, which
would need to check for nil as input?
> > Does anyone have an idea how I could bring a variable
> > n into the whole thing so that I could set the maximum length of the
> > sublists? [<== corrected --gjm]
> > This is currently kinda hardcoded :).
>
> Here's one way to think about it.
>
> You've got a bunch of items, and you already know all the
> sublists of length <= n-1. You can get all the sublists
> of length <= n by taking all the ones of length <= n-1
> and, for each, adding on all the items in your bunch.
> This gives you all but the empty list, so throw that in
> too.
The same explaination with different words. Much like lisp itself hehe.
> It's not too hard to turn this into a simple recursive
> function. My currently-preferred version is 4 lines long,
> but you'll learn faster if you work out how to do it
> for yourself. (Don't worry if it takes you more than
> 4 lines!)
My current version (see the other posting) is 11 lines without function
definition headers. But it adds a predication test.
Thanks for your tips.
> --
> Gareth McCaughan ················@pobox.com
> sig under construc
--
CYa,
Mario <·····@delysid.org>
Homepage(s): http://delysid.org | http://piss.at/
It's hard to tune heavily tuned code. :-)
-- Larry Wall in <·····················@wall.org>