Hello all. I'm learning Lisp, and would appreciate some critique of
my code. I decided to write a function to compute the cartesian
product of any number of sets.
(The code is in the Scheme dialect.)
;;; list-of-sets is a list of n sets of elements.
;;;
;;; cartesian-product returns a set of n-element tuples,
;;; formed by combining elements of each of the n sets.
;;; Specifically, the set of all tuples whose first element
;;; is from set1, second element is from set2, ... nth element is from
set n.
;;;
;;; The cardinality of the returned set =
;;; product of the cardilaties of each of the n-sets.
;;;
;;; For simplicity, lists, sets, and tuples are all represented as
Lisp lists.
;;;
;;; Example:
;;; (cartesian-product '( (1 2) (a b c) (d) ) )
;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
(define (cartesian-product. list-of-sets)
(define los list-of-sets)
(if (null? los)
'() ; The null cartesian-product is the empty set
(let
((first-set (car los))
(other-sets (cdr los)))
(if (null? other-sets)
(map list first-set)
(if (null? first-set)
'() ; If any of the n-sets are empty, their cartesian-
product is empty
(let
((first-element (car first-set))
(other-elements (cdr first-set)))
(append
(map (lambda (y) (cons first-element y)) (cartesian-
product other-sets))
(cartesian-product (cons other-elements other-
sets)))))))))
All comments - be they on the algo, simplicity, conventions, or style
- are appreciated. Two things strike me as akward about it already -
1. I would think that the algo should be much shorter and 2. tracing
it shows the code to calculate things quite inefficiently - but I'm
not sure how to improve it. Any comments appreciated.
Oops - that initial period shouldn't be there - it was part of a debug
tracer, as follows:
(define (cartesian-product los)
(let ((cp (cartesian-product. los)))
(display "(cartesian-product ")
(display los)
(display ") --> ")
(display cp)
(newline)
cp))
To run it without the tracer, make sure to replace "cartesian-
product." with "cartesian-product" in the original code.
"S. Robert James" <············@gmail.com> writes:
> Oops - that initial period shouldn't be there - it was part of a debug
> tracer, as follows:
>
> (define (cartesian-product los)
> (let ((cp (cartesian-product. los)))
> (display "(cartesian-product ")
> (display los)
> (display ") --> ")
> (display cp)
> (newline)
> cp))
>
> To run it without the tracer, make sure to replace "cartesian-
> product." with "cartesian-product" in the original code.
There are a few oddities in your code, like 'define' instead of
'defun'. :)
I guess you'd get better help in comp.lang.scheme instead.
/Andreas
--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
On Jan 22, 3:10 pm, Andreas Davour <·······@updateLIKE.uu.HELLse>
wrote:
> There are a few oddities in your code, like 'define' instead of
> 'defun'. :)
>
> I guess you'd get better help in comp.lang.scheme instead.
Glad to see that purism remains high.
On my newsreader, it says comp.lang.lisp (which Scheme is), not
comp.lang.commonlisp (which Scheme is not). There's not much activity
in the Scheme newsgroup, and anyway, beyond basic syntax, there's
nothing in my code which is in anyway Scheme specific.
Perhaps some kind hearted Lispers could put CL-versus-Scheme aside,
pretend I wrote 'defun' instead of 'define' and give me some help?
On Tue, 22 Jan 2008 12:53:59 -0800 (PST), "S. Robert James" <············@gmail.com> wrote:
> Glad to see that purism remains high.
>
> On my newsreader, it says comp.lang.lisp (which Scheme is), not
> comp.lang.commonlisp (which Scheme is not).
Are you here to get help or to pick a fight?
> There's not much activity in the Scheme newsgroup, and anyway,
> beyond basic syntax, there's nothing in my code which is in anyway
> Scheme specific.
>
> Perhaps some kind hearted Lispers could put CL-versus-Scheme aside,
> pretend I wrote 'defun' instead of 'define' and give me some help?
There's a lot more in your code than DEFINE that's Scheme-specific.
Edi.
--
European Common Lisp Meeting, Amsterdam, April 19/20, 2008
http://weitz.de/eclm2008/
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
S. Robert James wrote:
> On Jan 22, 3:10 pm, Andreas Davour <·······@updateLIKE.uu.HELLse>
> wrote:
>> There are a few oddities in your code, like 'define' instead of
>> 'defun'. :)
>>
>> I guess you'd get better help in comp.lang.scheme instead.
>
> Glad to see that purism remains high.
It doesn't have anything to do with purism. It's just a matter of fact
that you will get better help in comp.lang.scheme.
> On my newsreader, it says comp.lang.lisp (which Scheme is), not
> comp.lang.commonlisp (which Scheme is not). There's not much activity
> in the Scheme newsgroup, and anyway, beyond basic syntax, there's
> nothing in my code which is in anyway Scheme specific.
There is a focus on Common Lisp in comp.lang.lisp. Other Lisp dialects
are also welcome, but rarely discussed.
> Perhaps some kind hearted Lispers could put CL-versus-Scheme aside,
> pretend I wrote 'defun' instead of 'define' and give me some help?
(defun simple-cartesian-product (set list)
(loop for elm in set
nconc (loop for set in list
collect (cons elm set))))
(defun cartesian-product (&rest list-of-sets)
(reduce #'simple-cartesian-product list-of-sets
:from-end t
:initial-value '(())))
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Jan 22, 10:36 pm, Pascal Costanza <····@p-cos.net> wrote:
> S. Robert James wrote:
> > On Jan 22, 3:10 pm, Andreas Davour <·······@updateLIKE.uu.HELLse>
> > wrote:
> >> There are a few oddities in your code, like 'define' instead of
> >> 'defun'. :)
>
> >> I guess you'd get better help in comp.lang.scheme instead.
>
> > Glad to see that purism remains high.
>
> It doesn't have anything to do with purism. It's just a matter of fact
> that you will get better help in comp.lang.scheme.
>
> > On my newsreader, it says comp.lang.lisp (which Scheme is), not
> > comp.lang.commonlisp (which Scheme is not). There's not much activity
> > in the Scheme newsgroup, and anyway, beyond basic syntax, there's
> > nothing in my code which is in anyway Scheme specific.
>
> There is a focus on Common Lisp in comp.lang.lisp. Other Lisp dialects
> are also welcome, but rarely discussed.
>
> > Perhaps some kind hearted Lispers could put CL-versus-Scheme aside,
> > pretend I wrote 'defun' instead of 'define' and give me some help?
>
> (defun simple-cartesian-product (set list)
> (loop for elm in set
> nconc (loop for set in list
> collect (cons elm set))))
>
> (defun cartesian-product (&rest list-of-sets)
> (reduce #'simple-cartesian-product list-of-sets
> :from-end t
> :initial-value '(())))
>
> Pascal
>
> --
> 1st European Lisp Symposium (ELS'08)http://prog.vub.ac.be/~pcostanza/els08/
>
> My website:http://p-cos.net
> Common Lisp Document Repository:http://cdr.eurolisp.org
> Closer to MOP & ContextL:http://common-lisp.net/project/closer/
As other already pointed out your question belongs to scheme unless
you want to draw some comparasions. Here's some purely recursive, side-
effect free code I believe you could easily rewrite in scheme:
(defun cp-atom-list (a l)
(cond ((null l) nil)
(t (cons (cons a (car l))
(cp-atom-list a (cdr l))))))
(defun cp-list-list (m n)
(if (and m n)
(append (cp-atom-list (car m) n)
(cp-list-list (cdr m) n))
nil))
(defun cartesian-product (&rest list-of-sets)
(reduce #'cp-list-list list-of-sets
:from-end t
:initial-value '(())))
(cartesian-product '(1 2) '(a b c) '(d))
((1 A D) (1 B D) (1 C D) (2 A D) (2 B D) (2 C D))
(cartesian-product '(a b c) '(1 2 3) '($ %))
((A 1 $) (A 1 %) (A 2 $) (A 2 %) (A 3 $) (A 3 %) (B 1 $) (B 1 %) (B 2
$) (B 2 %) (B 3 $) (B 3 %) (C 1 $) (C 1 %) (C 2 $) (C 2 %) (C 3 $) (C
3 %))
cheers
Slobodan
Den Tue, 22 Jan 2008 15:42:51 -0800 skrev Slobodan Blazeski:
> On Jan 22, 10:36 pm, Pascal Costanza <····@p-cos.net> wrote:
[snip]
> As other already pointed out your question belongs to scheme unless you
> want to draw some comparasions. Here's some purely recursive, side-
> effect free code I believe you could easily rewrite in scheme:
Have you considered looking at what article you're quoting and replying
to? Maybe if you took the time to at least trim *the signature* from your
quotes...
Cheers,
Maciej
On Jan 23, 12:57 am, Maciej Katafiasz <········@gmail.com> wrote:
> Den Tue, 22 Jan 2008 15:42:51 -0800 skrev Slobodan Blazeski:
>
> > On Jan 22, 10:36 pm, Pascal Costanza <····@p-cos.net> wrote:
>
> [snip]
>
> > As other already pointed out your question belongs to scheme unless you
> > want to draw some comparasions. Here's some purely recursive, side-
> > effect free code I believe you could easily rewrite in scheme:
>
> Have you considered looking at what article you're quoting and replying
> to?
I wanted to reply to Pascals article since I copy pasted his 2nd
definition.
> Maybe if you took the time to at least trim *the signature* from your
> quotes...
That would be right thing to do , but googlegroups made me a lazy
bastard so I didn't do it.
cheers
Slobodan
>
> Cheers,
> Maciej
"S. Robert James" <············@gmail.com> writes:
> On Jan 22, 3:10�pm, Andreas Davour <·······@updateLIKE.uu.HELLse>
> wrote:
>> There are a few oddities in your code, like 'define' instead of
>> 'defun'. :)
>>
>> I guess you'd get better help in comp.lang.scheme instead.
>
> Glad to see that purism remains high.
>
> On my newsreader, it says comp.lang.lisp (which Scheme is), not
> comp.lang.commonlisp (which Scheme is not). There's not much activity
> in the Scheme newsgroup, and anyway, beyond basic syntax, there's
> nothing in my code which is in anyway Scheme specific.
>
> Perhaps some kind hearted Lispers could put CL-versus-Scheme aside,
> pretend I wrote 'defun' instead of 'define' and give me some help?
I was just trying to direct you to where you could the best
feedback. Though if you phrase your questions well, there are lot of
very knowledgeable persons here who can help you with scheme stuff. I'm
sadly not one of them. My knowledge of scheme have rotted away from
disuse. I also know nothing about maths.
Hope you got what you needed, though. Keep hacking! CL may be the main
focus of this group, but it's way better you hack scheme than C++... :-)
/Andreas
--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
On Jan 22, 8:53 pm, "S. Robert James" <············@gmail.com> wrote:
>
> Glad to see that purism remains high.
>
No one who uses CL gives a toss about purism (there more gratuitously
hacky languages - Perl for instance - but not substantially so).
No, instead, we care about get useful stuff done. And if you want to
get useful answers about Scheme code you would be much better asking
in a Scheme forum. That's a matter of fact, not purism.
As to this:
> beyond basic syntax, there's
> nothing in my code which is in anyway Scheme specific.
That's just not true. Experienced CL programmers would not write code
like that: there are substantial and important programming-style
differences between the language families.
On 22 Jan, 20:53, "S. Robert James" <············@gmail.com> wrote:
> On Jan 22, 3:10 pm, Andreas Davour <·······@updateLIKE.uu.HELLse>
> wrote:
>
> > There are a few oddities in your code, like 'define' instead of
> > 'defun'. :)
>
> > I guess you'd get better help in comp.lang.scheme instead.
>
> Glad to see that purism remains high.
>
> On my newsreader, it says comp.lang.lisp (which Scheme is), not
> comp.lang.commonlisp (which Scheme is not). There's not much activity
> in the Scheme newsgroup, and anyway, beyond basic syntax, there's
> nothing in my code which is in anyway Scheme specific.
>
> Perhaps some kind hearted Lispers could put CL-versus-Scheme aside,
> pretend I wrote 'defun' instead of 'define' and give me some help?
In Lisp, the 'poly' solution given by me below is
(DEFUN cprod (L) (poly 'cartprod L))
(DEFUN poly (F L)
(IF (= (LENGTH L) 2)
(FUNCALL F (CAR L) (CADR L))
(FUNCALL F (CAR L) (poly F (CDR L)))))
(DEFUN cartprod (V3 V4)
(IF (NULL V3) NIL
(APPEND (MAPCAR #'(LAMBDA (W) (LIST (CAR V3) W)) V4)
(cartprod (CDR V3) V4))))
MAPCAR is (I think) map in Scheme; what FUNCALL might be I don't know
e.g. (FUNCALL '+ 4 5) = 9.
Mark
On Jan 23, 7:26 am, Mark Tarver <··········@ukonline.co.uk> wrote:
>
> In Lisp, the 'poly' solution given by me below is
>
> (DEFUN cprod (L) (poly 'cartprod L))
>
> (DEFUN poly (F L)
> (IF (= (LENGTH L) 2)
> (FUNCALL F (CAR L) (CADR L))
> (FUNCALL F (CAR L) (poly F (CDR L)))))
>
> (DEFUN cartprod (V3 V4)
> (IF (NULL V3) NIL
> (APPEND (MAPCAR #'(LAMBDA (W) (LIST (CAR V3) W)) V4)
> (cartprod (CDR V3) V4))))
>
> MAPCAR is (I think) map in Scheme; what FUNCALL might be I don't know
> e.g. (FUNCALL '+ 4 5) = 9.
>
Scheme uses the primitive APPLY. APPLY is just like FUNCALL except
that the arguments must be in a list. This is Mark's POLY using
Common Lisp's Apply:
(defun poly (f l)
(if (= (length l) 2)
(apply F (list (car l) (cadr l)))
(apply F (list (car l) (poly f (cdr l))))))
Now you have a direct word for word translation to Scheme.
Also, did you try Googling the problem? I found this file "Comparative
Examples of Looping Idioms" by Taylor Campbell containing various
versions of the function CARTESIAN-PRODUCT :
http://mumble.net/~campbell/scheme/loop-comparison.scm
Your scheme to get help from cll seems to have paid off - this
time ;-)
agt
>
> Scheme uses the primitive APPLY. APPLY is just like FUNCALL except
> that the arguments must be in a list. This is Mark's POLY using
> Common Lisp's Apply:
Common Lisp has a function apply too. It works approx like the one in
Scheme I think.
--------------
John Thingstad
Thanks for all the good ideas - I'm following up on them.
To summarize the most important point that I picked up:
cartesian-product is best implemented as:
(define (binary-cp set-of-elements set-of-tuples)
...)
(define (cp set-of-sets-of-elements)
(if (null? set-of-sets-of-elements)
'(())
...reduce using binary-cp...)
This brought to my attention that Cartesian Products are not strictly
associative. That is, given A = {a} B = {b} and C = {c}, we have:
CP(CP(A,B),C) = { ((a,b),c) }
CP(A,CP(B,C)) = { (a,(b,c) }
Common usage of CP A B C - which I implemented - seems to be neither
of the above, but rather:
{ (a,b,c) }
P� Wed, 23 Jan 2008 13:26:03 +0100, skrev Mark Tarver
<··········@ukonline.co.uk>:
>
> MAPCAR is (I think) map in Scheme; what FUNCALL might be I don't know
> e.g. (FUNCALL '+ 4 5) = 9.
>
> Mark
In a lisp-1 funcall is unneccesary.
(let (inc (lambda (x) (+ x 1))
(inc 2))
-> 3
--------------
John Thingstad
On Jan 22, 8:49 pm, "S. Robert James" <············@gmail.com> wrote:
> Hello all. I'm learning Lisp, and would appreciate some critique of
> my code. I decided to write a function to compute the cartesian
> product of any number of sets.
>
> (The code is in the Scheme dialect.)
>
> ;;; list-of-sets is a list of n sets of elements.
> ;;;
> ;;; cartesian-product returns a set of n-element tuples,
> ;;; formed by combining elements of each of the n sets.
> ;;; Specifically, the set of all tuples whose first element
> ;;; is from set1, second element is from set2, ... nth element is from
> set n.
> ;;;
> ;;; The cardinality of the returned set =
> ;;; product of the cardilaties of each of the n-sets.
> ;;;
> ;;; For simplicity, lists, sets, and tuples are all represented as
> Lisp lists.
> ;;;
> ;;; Example:
> ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> (define (cartesian-product. list-of-sets)
> (define los list-of-sets)
> (if (null? los)
> '() ; The null cartesian-product is the empty set
> (let
> ((first-set (car los))
> (other-sets (cdr los)))
> (if (null? other-sets)
> (map list first-set)
> (if (null? first-set)
> '() ; If any of the n-sets are empty, their cartesian-
> product is empty
> (let
> ((first-element (car first-set))
> (other-elements (cdr first-set)))
> (append
> (map (lambda (y) (cons first-element y)) (cartesian-
> product other-sets))
> (cartesian-product (cons other-elements other-
> sets)))))))))
>
> All comments - be they on the algo, simplicity, conventions, or style
> - are appreciated. Two things strike me as akward about it already -
> 1. I would think that the algo should be much shorter and 2. tracing
> it shows the code to calculate things quite inefficiently - but I'm
> not sure how to improve it. Any comments appreciated.
Ok here it is the word by word translation from scheme to common lisp:
(defun cartesian-product (list-of-sets)
(let ((los list-of-sets))
(if (null los) nil
(let ((first-set (car los))
(other-sets (cdr los)))
(if (null other-sets)
(mapcar #'list first-set)
(if (null first-set) nil
(let ((first-element (car first-set))
(other-elements (cdr first-set)))
(append
(mapcar #'(lambda (y) (cons first-element y))
(cartesian-product other-sets))
(cartesian-product (cons other-elements other-
sets))))))))))
Here's my humble opinion but keep in mind that I have a bachelor in
financial management instead of CS:
Hm Once upon a time spy broke into pentagon and stole the last 23
pages of nuclear missile software that was accidentally written in
lisp(*) All of them were full of closing parenthesis
like ))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
so unless you have some pretty good reason why your code is overdoing
break it into a smaller functionalities. There's an excellent saying
from SICP lectures that if you can't know it's name you can't summon
it's magick. From your code I don't know what's doing what, unless I
really think hard what the hell you try to achieve. So it's probably
better to have smaller functions that could be easily tested and
maintaineed. Take a look at mine and pascals code for some hints.
BTW the advice about newsgroups still stands, if you want to learn
scheme better ask question in comp.lang.scheme , if you're interested
in common lisp or lisp family of languages in general or those who
don't separate newsgroup wellcome in c.l.l.
cheers
Slobodan
(*) When I use lisp in this newsgroup I mean a common lisp for other
meaning I use lisp family of languages.
On 22 Jan, 19:49, "S. Robert James" <············@gmail.com> wrote:
> Hello all. I'm learning Lisp, and would appreciate some critique of
> my code. I decided to write a function to compute the cartesian
> product of any number of sets.
>
> (The code is in the Scheme dialect.)
>
> ;;; list-of-sets is a list of n sets of elements.
> ;;;
> ;;; cartesian-product returns a set of n-element tuples,
> ;;; formed by combining elements of each of the n sets.
> ;;; Specifically, the set of all tuples whose first element
> ;;; is from set1, second element is from set2, ... nth element is from
> set n.
> ;;;
> ;;; The cardinality of the returned set =
> ;;; product of the cardilaties of each of the n-sets.
> ;;;
> ;;; For simplicity, lists, sets, and tuples are all represented as
> Lisp lists.
> ;;;
> ;;; Example:
> ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> (define (cartesian-product. list-of-sets)
> (define los list-of-sets)
> (if (null? los)
> '() ; The null cartesian-product is the empty set
> (let
> ((first-set (car los))
> (other-sets (cdr los)))
> (if (null? other-sets)
> (map list first-set)
> (if (null? first-set)
> '() ; If any of the n-sets are empty, their cartesian-
> product is empty
> (let
> ((first-element (car first-set))
> (other-elements (cdr first-set)))
> (append
> (map (lambda (y) (cons first-element y)) (cartesian-
> product other-sets))
> (cartesian-product (cons other-elements other-
> sets)))))))))
>
> All comments - be they on the algo, simplicity, conventions, or style
> - are appreciated. Two things strike me as akward about it already -
> 1. I would think that the algo should be much shorter and 2. tracing
> it shows the code to calculate things quite inefficiently - but I'm
> not sure how to improve it. Any comments appreciated.
Its a bit too long Robert; try this in Qi
(define cartprod
[] _ -> []
[X | Y] Z -> (append (map (/. W [X W]) Z) (cartprod Y Z)))
transcribed to Lisp
(DEFUN cartprod (V3 V4)
(COND ((NULL V3) NIL)
(T
(APPEND (MAPCAR #'(LAMBDA (W) (LIST (CAR V3) W)) V4)
(cartprod (CDR V3) V4)))))
Mark
On Jan 22, 7:59 pm, Mark Tarver <··········@ukonline.co.uk> wrote:
> On 22 Jan, 19:49, "S. Robert James" <············@gmail.com> wrote:
>
>
>
> > Hello all. I'm learning Lisp, and would appreciate some critique of
> > my code. I decided to write a function to compute the cartesian
> > product of any number of sets.
>
> > (The code is in the Scheme dialect.)
>
> > ;;; list-of-sets is a list of n sets of elements.
> > ;;;
> > ;;; cartesian-product returns a set of n-element tuples,
> > ;;; formed by combining elements of each of the n sets.
> > ;;; Specifically, the set of all tuples whose first element
> > ;;; is from set1, second element is from set2, ... nth element is from
> > set n.
> > ;;;
> > ;;; The cardinality of the returned set =
> > ;;; product of the cardilaties of each of the n-sets.
> > ;;;
> > ;;; For simplicity, lists, sets, and tuples are all represented as
> > Lisp lists.
> > ;;;
> > ;;; Example:
> > ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> > ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> > (define (cartesian-product. list-of-sets)
> > (define los list-of-sets)
> > (if (null? los)
> > '() ; The null cartesian-product is the empty set
> > (let
> > ((first-set (car los))
> > (other-sets (cdr los)))
> > (if (null? other-sets)
> > (map list first-set)
> > (if (null? first-set)
> > '() ; If any of the n-sets are empty, their cartesian-
> > product is empty
> > (let
> > ((first-element (car first-set))
> > (other-elements (cdr first-set)))
> > (append
> > (map (lambda (y) (cons first-element y)) (cartesian-
> > product other-sets))
> > (cartesian-product (cons other-elements other-
> > sets)))))))))
>
> > All comments - be they on the algo, simplicity, conventions, or style
> > - are appreciated. Two things strike me as akward about it already -
> > 1. I would think that the algo should be much shorter and 2. tracing
> > it shows the code to calculate things quite inefficiently - but I'm
> > not sure how to improve it. Any comments appreciated.
>
> Its a bit too long Robert; try this in Qi
>
> (define cartprod
> [] _ -> []
> [X | Y] Z -> (append (map (/. W [X W]) Z) (cartprod Y Z)))
>
> transcribed to Lisp
>
> (DEFUN cartprod (V3 V4)
> (COND ((NULL V3) NIL)
> (T
> (APPEND (MAPCAR #'(LAMBDA (W) (LIST (CAR V3) W)) V4)
> (cartprod (CDR V3) V4)))))
>
> Mark
With all due respect, Dr. Tarver, it seems that OP asked for a
different thing: to find a cartesian product of a list of n sets of
elements, while your function computes cartesian product for just two
sets.
I've come up with the following Qi solution - please correct me if I'm
wrong or if it could be simplified:
(define cartprod
[] -> []
[[] | _] -> []
[[X | Y]] -> [[X] | (cartprod [Y])]
[[X | Y] | Z] -> (append (map (/. W [X | W]) (cartprod Z))
(cartprod [Y | Z])))
(some tests are below). And here is the lisp dump:
(DEFUN cartprod (V11)
(COND ((NULL V11) NIL) ((AND (CONSP V11) (NULL (CAR V11))) NIL)
((AND (CONSP V11) (CONSP (CAR V11)) (NULL (CDR V11)))
(LET* ((V12 (CAR V11)))
(cons (LIST (CAR V12)) (cartprod (LIST (CDR V12))))))
((AND (CONSP V11) (CONSP (CAR V11)))
(LET* ((V13 (CAR V11)) (V14 (CDR V11)))
(APPEND
(THE LIST (map #'(LAMBDA (W) (cons (CAR V13) W)) (cartprod
V14)))
(cartprod (cons (CDR V13) V14)))))
(T (qi::f_error 'cartprod))))
Here are some test of cartprod:
(1-) (cartprod [])
[]
(2-) (cartprod [[1 2 3]])
[[1] [2] [3]]
(3-) (cartprod [[1 2 3] [4 5 6]])
[[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]
(4-) (cartprod [[1 2 3] [4 5 6] [d e]])
[[1 4 d] [1 4 e] [1 5 d] [1 5 e] [1 6 d] [1 6 e] [2 4 d] [2 4 e] [2 5
d]
[2 5 e] [2 6 d] [2 6 e] [3 4 d] [3 4 e] [3 5 d] [3 5 e] [3 6 d] [3 6
e]]
Best,
Victor.
On 23 Jan, 05:33, vtail <··············@gmail.com> wrote:
> On Jan 22, 7:59 pm, Mark Tarver <··········@ukonline.co.uk> wrote:
>
>
>
>
>
> > On 22 Jan, 19:49, "S. Robert James" <············@gmail.com> wrote:
>
> > > Hello all. I'm learning Lisp, and would appreciate some critique of
> > > my code. I decided to write a function to compute the cartesian
> > > product of any number of sets.
>
> > > (The code is in the Scheme dialect.)
>
> > > ;;; list-of-sets is a list of n sets of elements.
> > > ;;;
> > > ;;; cartesian-product returns a set of n-element tuples,
> > > ;;; formed by combining elements of each of the n sets.
> > > ;;; Specifically, the set of all tuples whose first element
> > > ;;; is from set1, second element is from set2, ... nth element is from
> > > set n.
> > > ;;;
> > > ;;; The cardinality of the returned set =
> > > ;;; product of the cardilaties of each of the n-sets.
> > > ;;;
> > > ;;; For simplicity, lists, sets, and tuples are all represented as
> > > Lisp lists.
> > > ;;;
> > > ;;; Example:
> > > ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> > > ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> > > (define (cartesian-product. list-of-sets)
> > > (define los list-of-sets)
> > > (if (null? los)
> > > '() ; The null cartesian-product is the empty set
> > > (let
> > > ((first-set (car los))
> > > (other-sets (cdr los)))
> > > (if (null? other-sets)
> > > (map list first-set)
> > > (if (null? first-set)
> > > '() ; If any of the n-sets are empty, their cartesian-
> > > product is empty
> > > (let
> > > ((first-element (car first-set))
> > > (other-elements (cdr first-set)))
> > > (append
> > > (map (lambda (y) (cons first-element y)) (cartesian-
> > > product other-sets))
> > > (cartesian-product (cons other-elements other-
> > > sets)))))))))
>
> > > All comments - be they on the algo, simplicity, conventions, or style
> > > - are appreciated. Two things strike me as akward about it already -
> > > 1. I would think that the algo should be much shorter and 2. tracing
> > > it shows the code to calculate things quite inefficiently - but I'm
> > > not sure how to improve it. Any comments appreciated.
>
> > Its a bit too long Robert; try this in Qi
>
> > (define cartprod
> > [] _ -> []
> > [X | Y] Z -> (append (map (/. W [X W]) Z) (cartprod Y Z)))
>
> > transcribed to Lisp
>
> > (DEFUN cartprod (V3 V4)
> > (COND ((NULL V3) NIL)
> > (T
> > (APPEND (MAPCAR #'(LAMBDA (W) (LIST (CAR V3) W)) V4)
> > (cartprod (CDR V3) V4)))))
>
> > Mark
>
> With all due respect, Dr. Tarver, it seems that OP asked for a
> different thing: to find a cartesian product of a list of n sets of
> elements, while your function computes cartesian product for just two
> sets.
>
> I've come up with the following Qi solution - please correct me if I'm
> wrong or if it could be simplified:
>
> (define cartprod
> [] -> []
> [[] | _] -> []
> [[X | Y]] -> [[X] | (cartprod [Y])]
> [[X | Y] | Z] -> (append (map (/. W [X | W]) (cartprod Z))
> (cartprod [Y | Z])))
>
> (some tests are below). And here is the lisp dump:
>
> (DEFUN cartprod (V11)
> (COND ((NULL V11) NIL) ((AND (CONSP V11) (NULL (CAR V11))) NIL)
> ((AND (CONSP V11) (CONSP (CAR V11)) (NULL (CDR V11)))
> (LET* ((V12 (CAR V11)))
> (cons (LIST (CAR V12)) (cartprod (LIST (CDR V12))))))
> ((AND (CONSP V11) (CONSP (CAR V11)))
> (LET* ((V13 (CAR V11)) (V14 (CDR V11)))
> (APPEND
> (THE LIST (map #'(LAMBDA (W) (cons (CAR V13) W)) (cartprod
> V14)))
> (cartprod (cons (CDR V13) V14)))))
> (T (qi::f_error 'cartprod))))
>
> Here are some test of cartprod:
>
> (1-) (cartprod [])
> []
>
> (2-) (cartprod [[1 2 3]])
> [[1] [2] [3]]
>
> (3-) (cartprod [[1 2 3] [4 5 6]])
> [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]
>
> (4-) (cartprod [[1 2 3] [4 5 6] [d e]])
> [[1 4 d] [1 4 e] [1 5 d] [1 5 e] [1 6 d] [1 6 e] [2 4 d] [2 4 e] [2 5
> d]
> [2 5 e] [2 6 d] [2 6 e] [3 4 d] [3 4 e] [3 5 d] [3 5 e] [3 6 d] [3 6
> e]]
>
> Best,
> Victor.- Hide quoted text -
>
> - Show quoted text -
Indeed, I missed his rider about wanting the product for n sets.
Generally though, the generalisation of a binary operation to the n-
ary case is not difficult once you have defined the binary case. The
following higher-order function does this; generalising any binary
operation to the general case.
(define poly
F [X Y] -> (F X Y)
F [W X Y | Z] -> (F W (poly F [X Y | Z])))
So one solution is then
(define cprods
X -> (poly cartprod X))
(cprods [[1 2 ] [a b] [3 4]]) =
[[1 [a 3]] [1 [a 4]] [1 [b 3]] [1 [b 4]] [2 [a 3]] [2 [a 4]] [2 [b
3]] [2 [b 4]]]
This solution, while correct, produces a Cartesian product that nests
ever more deeply as n increases. It treats A*B*C as A*(B * C). Some
people prefer to flatten this product and your solution looks to be in
that category.
best
Mark
On 23 Jan, 10:28, Mark Tarver <··········@ukonline.co.uk> wrote:
> On 23 Jan, 05:33, vtail <··············@gmail.com> wrote:
>
>
>
>
>
> > On Jan 22, 7:59 pm, Mark Tarver <··········@ukonline.co.uk> wrote:
>
> > > On 22 Jan, 19:49, "S. Robert James" <············@gmail.com> wrote:
>
> > > > Hello all. I'm learning Lisp, and would appreciate some critique of
> > > > my code. I decided to write a function to compute the cartesian
> > > > product of any number of sets.
>
> > > > (The code is in the Scheme dialect.)
>
> > > > ;;; list-of-sets is a list of n sets of elements.
> > > > ;;;
> > > > ;;; cartesian-product returns a set of n-element tuples,
> > > > ;;; formed by combining elements of each of the n sets.
> > > > ;;; Specifically, the set of all tuples whose first element
> > > > ;;; is from set1, second element is from set2, ... nth element is from
> > > > set n.
> > > > ;;;
> > > > ;;; The cardinality of the returned set =
> > > > ;;; product of the cardilaties of each of the n-sets.
> > > > ;;;
> > > > ;;; For simplicity, lists, sets, and tuples are all represented as
> > > > Lisp lists.
> > > > ;;;
> > > > ;;; Example:
> > > > ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> > > > ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> > > > (define (cartesian-product. list-of-sets)
> > > > (define los list-of-sets)
> > > > (if (null? los)
> > > > '() ; The null cartesian-product is the empty set
> > > > (let
> > > > ((first-set (car los))
> > > > (other-sets (cdr los)))
> > > > (if (null? other-sets)
> > > > (map list first-set)
> > > > (if (null? first-set)
> > > > '() ; If any of the n-sets are empty, their cartesian-
> > > > product is empty
> > > > (let
> > > > ((first-element (car first-set))
> > > > (other-elements (cdr first-set)))
> > > > (append
> > > > (map (lambda (y) (cons first-element y)) (cartesian-
> > > > product other-sets))
> > > > (cartesian-product (cons other-elements other-
> > > > sets)))))))))
>
> > > > All comments - be they on the algo, simplicity, conventions, or style
> > > > - are appreciated. Two things strike me as akward about it already -
> > > > 1. I would think that the algo should be much shorter and 2. tracing
> > > > it shows the code to calculate things quite inefficiently - but I'm
> > > > not sure how to improve it. Any comments appreciated.
>
> > > Its a bit too long Robert; try this in Qi
>
> > > (define cartprod
> > > [] _ -> []
> > > [X | Y] Z -> (append (map (/. W [X W]) Z) (cartprod Y Z)))
>
> > > transcribed to Lisp
>
> > > (DEFUN cartprod (V3 V4)
> > > (COND ((NULL V3) NIL)
> > > (T
> > > (APPEND (MAPCAR #'(LAMBDA (W) (LIST (CAR V3) W)) V4)
> > > (cartprod (CDR V3) V4)))))
>
> > > Mark
>
> > With all due respect, Dr. Tarver, it seems that OP asked for a
> > different thing: to find a cartesian product of a list of n sets of
> > elements, while your function computes cartesian product for just two
> > sets.
>
> > I've come up with the following Qi solution - please correct me if I'm
> > wrong or if it could be simplified:
>
> > (define cartprod
> > [] -> []
> > [[] | _] -> []
> > [[X | Y]] -> [[X] | (cartprod [Y])]
> > [[X | Y] | Z] -> (append (map (/. W [X | W]) (cartprod Z))
> > (cartprod [Y | Z])))
>
> > (some tests are below). And here is the lisp dump:
>
> > (DEFUN cartprod (V11)
> > (COND ((NULL V11) NIL) ((AND (CONSP V11) (NULL (CAR V11))) NIL)
> > ((AND (CONSP V11) (CONSP (CAR V11)) (NULL (CDR V11)))
> > (LET* ((V12 (CAR V11)))
> > (cons (LIST (CAR V12)) (cartprod (LIST (CDR V12))))))
> > ((AND (CONSP V11) (CONSP (CAR V11)))
> > (LET* ((V13 (CAR V11)) (V14 (CDR V11)))
> > (APPEND
> > (THE LIST (map #'(LAMBDA (W) (cons (CAR V13) W)) (cartprod
> > V14)))
> > (cartprod (cons (CDR V13) V14)))))
> > (T (qi::f_error 'cartprod))))
>
> > Here are some test of cartprod:
>
> > (1-) (cartprod [])
> > []
>
> > (2-) (cartprod [[1 2 3]])
> > [[1] [2] [3]]
>
> > (3-) (cartprod [[1 2 3] [4 5 6]])
> > [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]
>
> > (4-) (cartprod [[1 2 3] [4 5 6] [d e]])
> > [[1 4 d] [1 4 e] [1 5 d] [1 5 e] [1 6 d] [1 6 e] [2 4 d] [2 4 e] [2 5
> > d]
> > [2 5 e] [2 6 d] [2 6 e] [3 4 d] [3 4 e] [3 5 d] [3 5 e] [3 6 d] [3 6
> > e]]
>
> > Best,
> > Victor.- Hide quoted text -
>
> > - Show quoted text -
>
> Indeed, I missed his rider about wanting the product for n sets.
>
> Generally though, the generalisation of a binary operation to the n-
> ary case is not difficult once you have defined the binary case. The
> following higher-order function does this; generalising any binary
> operation to the general case.
>
> (define poly
> F [X Y] -> (F X Y)
> F [W X Y | Z] -> (F W (poly F [X Y | Z])))
>
> So one solution is then
>
> (define cprods
> X -> (poly cartprod X))
>
> (cprods [[1 2 ] [a b] [3 4]]) =
> [[1 [a 3]] [1 [a 4]] [1 [b 3]] [1 [b 4]] [2 [a 3]] [2 [a 4]] [2 [b
> 3]] [2 [b 4]]]
>
> This solution, while correct, produces a Cartesian product that nests
> ever more deeply as n increases. It treats A*B*C as A*(B * C). Some
> people prefer to flatten this product and your solution looks to be in
> that category.
>
> best
>
> Mark- Hide quoted text -
>
> - Show quoted text -
P.S. The flattened product version is actually more difficult so good
for you.
Mark
Den Tue, 22 Jan 2008 11:49:11 -0800 skrev S. Robert James:
> Hello all. I'm learning Lisp, and would appreciate some critique of my
> code. I decided to write a function to compute the cartesian product of
> any number of sets.
>
> (The code is in the Scheme dialect.)
Scheme is indeed a Lisp dialect, but this newsgroup concerns itself
primarly with Common Lisp. You will get much better results in
comp.lang.scheme. Or you could pick up CL, that works too, and is by all
means a noble endeavour :).
Cheers,
Maciej
S. Robert James wrote:
> Hello all. I'm learning Lisp, and would appreciate some critique of
> my code. I decided to write a function to compute the cartesian
> product of any number of sets.
>
> (The code is in the Scheme dialect.)
>
> ;;; list-of-sets is a list of n sets of elements.
> ;;;
> ;;; cartesian-product returns a set of n-element tuples,
> ;;; formed by combining elements of each of the n sets.
> ;;; Specifically, the set of all tuples whose first element
> ;;; is from set1, second element is from set2, ... nth element is from
> set n.
> ;;;
> ;;; The cardinality of the returned set =
> ;;; product of the cardilaties of each of the n-sets.
> ;;;
> ;;; For simplicity, lists, sets, and tuples are all represented as
> Lisp lists.
> ;;;
> ;;; Example:
> ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> (define (cartesian-product. list-of-sets)
> (define los list-of-sets)
> (if (null? los)
> '() ; The null cartesian-product is the empty set
> (let
> ((first-set (car los))
> (other-sets (cdr los)))
> (if (null? other-sets)
> (map list first-set)
> (if (null? first-set)
> '() ; If any of the n-sets are empty, their cartesian-
> product is empty
> (let
> ((first-element (car first-set))
> (other-elements (cdr first-set)))
> (append
> (map (lambda (y) (cons first-element y)) (cartesian-
> product other-sets))
> (cartesian-product (cons other-elements other-
> sets)))))))))
>
>
> All comments - be they on the algo, simplicity, conventions, or style
> - are appreciated. Two things strike me as akward about it already -
> 1. I would think that the algo should be much shorter and 2. tracing
> it shows the code to calculate things quite inefficiently - but I'm
> not sure how to improve it. Any comments appreciated.
This is how a pro would do it in CL:
PoAIP, Norvig, pg.47
--
They call me the
Cautionary Whale.
On Jan 22, 3:17 pm, vanekl <·····@acd.net> wrote:
> S. Robert James wrote:
> > Hello all. I'm learning Lisp, and would appreciate some critique of
> > my code. I decided to write a function to compute the cartesian
> > product of any number of sets.
>
> > (The code is in the Scheme dialect.)
>
> > ;;; list-of-sets is a list of n sets of elements.
> > ;;;
> > ;;; cartesian-product returns a set of n-element tuples,
> > ;;; formed by combining elements of each of the n sets.
> > ;;; Specifically, the set of all tuples whose first element
> > ;;; is from set1, second element is from set2, ... nth element is from
> > set n.
> > ;;;
> > ;;; The cardinality of the returned set =
> > ;;; product of the cardilaties of each of the n-sets.
> > ;;;
> > ;;; For simplicity, lists, sets, and tuples are all represented as
> > Lisp lists.
> > ;;;
> > ;;; Example:
> > ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> > ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> > (define (cartesian-product. list-of-sets)
> > (define los list-of-sets)
> > (if (null? los)
> > '() ; The null cartesian-product is the empty set
> > (let
> > ((first-set (car los))
> > (other-sets (cdr los)))
> > (if (null? other-sets)
> > (map list first-set)
> > (if (null? first-set)
> > '() ; If any of the n-sets are empty, their cartesian-
> > product is empty
> > (let
> > ((first-element (car first-set))
> > (other-elements (cdr first-set)))
> > (append
> > (map (lambda (y) (cons first-element y)) (cartesian-
> > product other-sets))
> > (cartesian-product (cons other-elements other-
> > sets)))))))))
>
> > All comments - be they on the algo, simplicity, conventions, or style
> > - are appreciated. Two things strike me as akward about it already -
> > 1. I would think that the algo should be much shorter and 2. tracing
> > it shows the code to calculate things quite inefficiently - but I'm
> > not sure how to improve it. Any comments appreciated.
>
> This is how a pro would do it in CL:
> PoAIP, Norvig, pg.47
If you mean (cross-product #'list xlist ylist) - it only works for two
sets.
vtail wrote:
> On Jan 22, 3:17 pm, vanekl <·····@acd.net> wrote:
>> S. Robert James wrote:
>>> Hello all. I'm learning Lisp, and would appreciate some critique of
>>> my code. I decided to write a function to compute the cartesian
>>> product of any number of sets.
>>> (The code is in the Scheme dialect.)
>>> ;;; list-of-sets is a list of n sets of elements.
>>> ;;;
>>> ;;; cartesian-product returns a set of n-element tuples,
>>> ;;; formed by combining elements of each of the n sets.
>>> ;;; Specifically, the set of all tuples whose first element
>>> ;;; is from set1, second element is from set2, ... nth element is from
>>> set n.
>>> ;;;
>>> ;;; The cardinality of the returned set =
>>> ;;; product of the cardilaties of each of the n-sets.
>>> ;;;
>>> ;;; For simplicity, lists, sets, and tuples are all represented as
>>> Lisp lists.
>>> ;;;
>>> ;;; Example:
>>> ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
>>> ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
>>> (define (cartesian-product. list-of-sets)
>>> (define los list-of-sets)
>>> (if (null? los)
>>> '() ; The null cartesian-product is the empty set
>>> (let
>>> ((first-set (car los))
>>> (other-sets (cdr los)))
>>> (if (null? other-sets)
>>> (map list first-set)
>>> (if (null? first-set)
>>> '() ; If any of the n-sets are empty, their cartesian-
>>> product is empty
>>> (let
>>> ((first-element (car first-set))
>>> (other-elements (cdr first-set)))
>>> (append
>>> (map (lambda (y) (cons first-element y)) (cartesian-
>>> product other-sets))
>>> (cartesian-product (cons other-elements other-
>>> sets)))))))))
>>> All comments - be they on the algo, simplicity, conventions, or style
>>> - are appreciated. Two things strike me as akward about it already -
>>> 1. I would think that the algo should be much shorter and 2. tracing
>>> it shows the code to calculate things quite inefficiently - but I'm
>>> not sure how to improve it. Any comments appreciated.
>> This is how a pro would do it in CL:
>> PoAIP, Norvig, pg.47
>
> If you mean (cross-product #'list xlist ylist) - it only works for two
> sets.
CL-USER[2]: (combine-all (combine-all '((1) (2)) '((a) (b) (c)) ) '((d)) )
((1 A D) (2 A D) (1 B D) (2 B D) (1 C D) (2 C D))
On Tue, 22 Jan 2008 11:49:11 -0800 (PST), "S. Robert James"
<············@gmail.com> wrote:
>Hello all. I'm learning Lisp, and would appreciate some critique of
>my code. I decided to write a function to compute the cartesian
>product of any number of sets.
>
>(The code is in the Scheme dialect.)
>
>;;; list-of-sets is a list of n sets of elements.
>;;;
>;;; cartesian-product returns a set of n-element tuples,
>;;; formed by combining elements of each of the n sets.
>;;; Specifically, the set of all tuples whose first element
>;;; is from set1, second element is from set2, ... nth element is from
>set n.
>;;;
>;;; The cardinality of the returned set =
>;;; product of the cardilaties of each of the n-sets.
>;;;
>;;; For simplicity, lists, sets, and tuples are all represented as
>Lisp lists.
>;;;
>;;; Example:
>;;; (cartesian-product '( (1 2) (a b c) (d) ) )
>;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
>(define (cartesian-product. list-of-sets)
> (define los list-of-sets)
> (if (null? los)
> '() ; The null cartesian-product is the empty set
> (let
> ((first-set (car los))
> (other-sets (cdr los)))
> (if (null? other-sets)
> (map list first-set)
> (if (null? first-set)
> '() ; If any of the n-sets are empty, their cartesian-
>product is empty
> (let
> ((first-element (car first-set))
> (other-elements (cdr first-set)))
> (append
> (map (lambda (y) (cons first-element y)) (cartesian-
>product other-sets))
> (cartesian-product (cons other-elements other-
>sets)))))))))
>
>
>All comments - be they on the algo, simplicity, conventions, or style
>- are appreciated. Two things strike me as akward about it already -
>1. I would think that the algo should be much shorter and 2. tracing
>it shows the code to calculate things quite inefficiently - but I'm
>not sure how to improve it. Any comments appreciated.
There's probably a more succinct way to code it, but the following is
reasonably straight-forward.
(define (product-of-2 set1 set2)
(if (not (and (list? set1) (list? set2)))
(display "usage: (product-of-2 <set1> <set2>)\n")
(let %product ((set1 set1)
(set2 set2)
(result '()))
(if (null? set1)
result
(let* ((first (car set1))
(mapfunc (?(x)
(if (list? first)
(append first (list x))
(list first x)))))
(%product (cdr set1)
set2
(append result (map mapfunc set2)))
)))))
(define cartesian-product
(lambda sets
(if (not (and (list? sets) (>= (length sets) 2)
(andmap list? sets)))
(display "usage: (cartesian-product <set1> <set2> ...)\n")
(let %product ((set1 (car sets))
(sets (cdr sets)))
(if (null? sets)
set1
(%product (product-of-2 set1 (car sets))
(cdr sets))
))
)))
Use of append, unfortunately, is necessary to get the results in
flattened form. Both functions could also be written rather
straight-forwardly without helping functions using a loop and set! ...
but since you're working in Scheme I figured you'd want to see a more
functional approach.
George
--
for email reply remove "/" from address
S Robert James <············@gmail.com> wrote:
«Hello all. I'm learning Lisp, and would appreciate some critique of
my code. I decided to write a function to compute the cartesian
product of any number of sets.»
In Mathematica, this is one-line solution with the built-in function
Outer.
In[1]:=
·······@Outer[f,{3,4},{a,b},{x,y,z}]
Out[1]=
{f[3,a,x],f[3,a,y],f[3,a,z],f[3,b,x],f[3,b,y],f[3,b,z],f[4,a,x],f[4,a,y],
f[4,a,z],f[4,b,x],f[4,b,y],f[4,b,z]}
If you don't want the result flattened and want to keep the info of
the dimensions, just don't use Flatten above.
If you have more sets, just put them inside Outer. If you want the
result be list and not f, just do this then:
·······@Outer[f, {3, 4}, {a, b}, {x, y, z}] /. f -> List
The “f->List” means replace all symbol f by List.
You could use List as the first argument in Outer instead of f. But
that way is usually more complicated because then you have to flatten
the result with a second argument specifying how many level of nesting
to flatten. Like this:
In[16]:=
Flatten[Outer[List,{3,4},{a,b},{x,y,z}],2]
Out[16]=
{{3,a,x},{3,a,y},{3,a,z},{3,b,x},{3,b,y},{3,b,z},{4,a,x},{4,a,y},
{4,a,z},{4,b,
x},{4,b,y},{4,b,z}}
However, if the number of sets changes, then the flatten level also
changes, so it's a bit more code. (if the num of sets is n, then you
want flatten by n-1) The “f->List” is typically the simplist solution.
Btw, all the notation is a FullForm, which is kinda like lispy form.
e.g.
In[5]:=
········@HoldForm[·······@Outer[f,{3,4},{a,b},{x,y,z}]/.f->List]
Out[5]//FullForm=
HoldForm[ReplaceAll[Flatten[Outer[f,List[3,4],List[a,b],List[x,y,z]]],
Rule[f,List]]]
You might be curious why the “Outer” name. The Outer is a
generalization of the outer product in algebra.
Wikipedia has a nice article here:
http://en.wikipedia.org/wiki/Outer_product
Here's the doc for Outer:
http://reference.wolfram.com/mathematica/ref/Outer.html
---------------------------
PS btw, i just noticed that about 1/3 of the 28 posts in this thread
who's sole content is drivel by the common lisping fuckheads. Please
disregard them. The fight is typical.
Xah
···@xahlee.org
∑ http://xahlee.org/
☄
On Jan 22, 11:49 am, "S. Robert James" <············@gmail.com> wrote:
> Hello all. I'm learning Lisp, and would appreciate some critique of
> my code. I decided to write a function to compute the cartesian
> product of any number of sets.
>
> (The code is in the Scheme dialect.)
>
> ;;; list-of-sets is a list of n sets of elements.
> ;;;
> ;;; cartesian-product returns a set of n-element tuples,
> ;;; formed by combining elements of each of the n sets.
> ;;; Specifically, the set of all tuples whose first element
> ;;; is from set1, second element is from set2, ... nth element is from
> set n.
> ;;;
> ;;; The cardinality of the returned set =
> ;;; product of the cardilaties of each of the n-sets.
> ;;;
> ;;; For simplicity, lists, sets, and tuples are all represented as
> Lisp lists.
> ;;;
> ;;; Example:
> ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> (define (cartesian-product. list-of-sets)
> (define los list-of-sets)
> (if (null? los)
> '() ; The null cartesian-product is the empty set
> (let
> ((first-set (car los))
> (other-sets (cdr los)))
> (if (null? other-sets)
> (map list first-set)
> (if (null? first-set)
> '() ; If any of the n-sets are empty, their cartesian-
> product is empty
> (let
> ((first-element (car first-set))
> (other-elements (cdr first-set)))
> (append
> (map (lambda (y) (cons first-element y)) (cartesian-
> product other-sets))
> (cartesian-product (cons other-elements other-
> sets)))))))))
>
> All comments - be they on the algo, simplicity, conventions, or style
> - are appreciated. Two things strike me as akward about it already -
> 1. I would think that the algo should be much shorter and 2. tracing
> it shows the code to calculate things quite inefficiently - but I'm
> not sure how to improve it. Any comments appreciated.
"S. Robert James" <············@gmail.com> writes:
> Hello all. I'm learning Lisp, and would appreciate some critique of
> my code. I decided to write a function to compute the cartesian
> product of any number of sets.
>
> All comments - be they on the algo, simplicity, conventions, or style
> - are appreciated. Two things strike me as akward about it already -
> 1. I would think that the algo should be much shorter and 2. tracing
> it shows the code to calculate things quite inefficiently - but I'm
> not sure how to improve it. Any comments appreciated.
The cartesian product of two sets is easy enough, which
suggests using a fold to lift the operation from binary to
n-ary. There is a snag.
{a, b} x {1, 2} = {(a, 1), (a, 2), (b, 1), (b, 2)}
so strictly speaking
{a, b} x {1, 2} x {p, q}
is
( {a, b} x {1, 2} ) x {p, q} =
{((a, 1), p), ((a, 2), p), ((b, 1), p), ((b, 2), p),
((a, 1), q), ((a, 2), q), ((b, 1), q), ((b, 2), q)}
a technicality which mathematicians think of as /hair/ and
try to avoid or shave off.
The exact detail of the pair construction operator matters. I've
written my code to forground this detail
#| Start from a generalisation of the cartesian product of two sets, so that
f, {a,b}, {x,y} => {f(a,x), f(a,y), f(b,x), f(b,y)} |#
(defun product-set (f)
(lambda (u v)
(let (w)
(dolist (x u w)
(dolist (y v)
(push (funcall f x y) w))))))
#| I think this function has a clear theme
(funcall (product-set #'*) '(1 2 3) '(5 7))
=> (21 15 14 10 7 5)
|#
;;; Minor utility function, turns an item into a set
;;; with two elements, the singleton set and the empty set
;;; (in-and-out 3) => ((3) NIL)
(defun in-and-out (x)
"x => ({x} {})"
(list (list x) nil))
;;; Now we can define power-set and cartesian-product as folds
;;; that is, we use REDUCE to raise a suitably chosen product-set function
;;; from binary to n-ary
;;; (power-set '(1 2 3)) => ((2 1) (2 1 3) (1) (1 3) (2) (2 3) NIL (3))
(defun power-set (set)
(reduce (product-set #'union)
(mapcar #'in-and-out set)))
;;; (cartesian-product '(0) '(1 2) '(3 4 5))
;;; => ((0 1 5) (0 1 4) (0 1 3) (0 2 5) (0 2 4) (0 2 3))
(defun cartesian-product (&rest sets)
(reduce (product-set #'cons)
sets
:from-end t
:initial-value (list nil)))
Alan Crowe
Edinburgh
Scotland
Alan Crowe wrote:
...
>
> The cartesian product of two sets is easy enough, which
> suggests using a fold to lift the operation from binary to
> n-ary. There is a snag.
>
> {a, b} x {1, 2} = {(a, 1), (a, 2), (b, 1), (b, 2)}
>
> so strictly speaking
>
> {a, b} x {1, 2} x {p, q}
>
> is
>
> ( {a, b} x {1, 2} ) x {p, q} =
>
> {((a, 1), p), ((a, 2), p), ((b, 1), p), ((b, 2), p),
> ((a, 1), q), ((a, 2), q), ((b, 1), q), ((b, 2), q)}
>
> a technicality which mathematicians think of as /hair/ and
> try to avoid or shave off.
>
> The exact detail of the pair construction operator matters. I've
> written my code to forground this detail
>
> #| Start from a generalisation of the cartesian product of two sets, so that
> f, {a,b}, {x,y} => {f(a,x), f(a,y), f(b,x), f(b,y)} |#
>
> (defun product-set (f)
> (lambda (u v)
> (let (w)
> (dolist (x u w)
> (dolist (y v)
> (push (funcall f x y) w))))))
>
> #| I think this function has a clear theme
>
> (funcall (product-set #'*) '(1 2 3) '(5 7))
> => (21 15 14 10 7 5)
>
> |#
>
> ;;; Minor utility function, turns an item into a set
> ;;; with two elements, the singleton set and the empty set
> ;;; (in-and-out 3) => ((3) NIL)
> (defun in-and-out (x)
> "x => ({x} {})"
> (list (list x) nil))
>
> ;;; Now we can define power-set and cartesian-product as folds
> ;;; that is, we use REDUCE to raise a suitably chosen product-set function
> ;;; from binary to n-ary
>
> ;;; (power-set '(1 2 3)) => ((2 1) (2 1 3) (1) (1 3) (2) (2 3) NIL (3))
>
> (defun power-set (set)
> (reduce (product-set #'union)
> (mapcar #'in-and-out set)))
>
> ;;; (cartesian-product '(0) '(1 2) '(3 4 5))
> ;;; => ((0 1 5) (0 1 4) (0 1 3) (0 2 5) (0 2 4) (0 2 3))
>
> (defun cartesian-product (&rest sets)
> (reduce (product-set #'cons)
> sets
> :from-end t
> :initial-value (list nil)))
>
> Alan Crowe
> Edinburgh
> Scotland
+1
"S. Robert James" <············@gmail.com> writes:
> Hello all. I'm learning Lisp, and would appreciate some critique of my code.
> ;;; cartesian-product returns a set of n-element tuples,
> ;;; formed by combining elements of each of the n sets.
> ;;; Specifically, the set of all tuples whose first element
> ;;; is from set1, second element is from set2, ... nth element is from set n.
> ;;; For simplicity, lists, sets, and tuples are all represented as Lisp lists.
> ;;; Example:
> ;;; (cartesian-product '( (1 2) (a b c) (d) ) )
> ;;; --> ((1 a d) (1 b d) (1 c d) (2 a d) (2 b d) (2 c d))
> (define (cartesian-product. list-of-sets)
> (define los list-of-sets)
> (if (null? los)
> '() ; The null cartesian-product is the empty set
> (let
> ((first-set (car los))
> (other-sets (cdr los)))
> (if (null? other-sets)
> (map list first-set)
> (if (null? first-set)
> '() ; If any of the n-sets are empty, their cartesian-
> product is empty
> (let
> ((first-element (car first-set))
> (other-elements (cdr first-set)))
> (append
> (map (lambda (y) (cons first-element y)) (cartesian-
> product other-sets))
> (cartesian-product (cons other-elements other-
> sets)))))))))
Using higher order functions, I wrote this :
(defun cartesian* (&rest sets)
(reduce
(lambda (xs ys)
(mapcan
(lambda (x)
(mapcar
(lambda (y)
(cons x y))
ys))
xs))
sets
:initial-value '(()) :from-end t))
--
Take it Easy Don't Hurry Be Happy
Thierry
�������o�o��������o�o��������o�o��������o�o��������o�o�������