Does there exist a lisp function that has the following effect?
> (cross '(1 2 3) '(4 5 6))
((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
Thanks,
Shaun
No, but you can write it yourself easily. Here are two different
versions:
(defun cross (a b)
(mapcan #'(lambda (a-element)
(mapcar #'(lambda (b-element)
(list a-element b-element))
b))
a))
(defun cross (a b)
(loop for a-element in a
nconc (loop for b-element in b
collect `(,a-element ,b-element))))
Tim
On Thu, 10 May 2001, Shaun Jackman wrote:
> Does there exist a lisp function that has the following effect?
>
> > (cross '(1 2 3) '(4 5 6))
> ((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
>
> Thanks,
> Shaun
>
>
>
Shaun Jackman <········@nospam.home.com> writes:
> Does there exist a lisp function that has the following effect?
>
> > (cross '(1 2 3) '(4 5 6))
> ((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
One way to do it is with MAPCAR and MAPCAN. That's all the help you
get until you say if it's homework. If it IS homework, please show a
sample of what you've tried so far.
Kent M Pitman wrote:
> Shaun Jackman <········@nospam.home.com> writes:
>
>> Does there exist a lisp function that has the following effect?
>>
>> > (cross '(1 2 3) '(4 5 6))
>> ((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
>
> One way to do it is with MAPCAR and MAPCAN. That's all the help you
> get until you say if it's homework. If it IS homework, please show a
> sample of what you've tried so far.
No, it's not home work. I'm just experimenting with lisp a bit. It seemed
like a likely library function for a language so built around lists.
This is what I tried....
(defun cross (a b) (dolist (x a) (dolist (y b) (print `(,x ,y)))))
It seems to be in the right direction, but I don't want to print the items,
I want to return a list of them. I couldn't find an easy way to accomplish
this.
Shaun
In article <························@news1.rdc1.bc.home.com>, Shaun
Jackman <········@nospam.home.com> wrote:
>This is what I tried....
>(defun cross (a b) (dolist (x a) (dolist (y b) (print `(,x ,y)))))
>It seems to be in the right direction, but I don't want to print the items,
>I want to return a list of them. I couldn't find an easy way to accomplish
>this.
You're on the right track. You need to accumulate the pairs as you
create them. A common way to do it is:
? (defun cross (a b)
(let ((crosses nil))
(dolist (x a)
(dolist (y b)
(push (list x y) crosses)))
(nreverse crosses)))
CROSS
? (cross '(1 2 3) '(4 5 6))
((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
The variable "crosses" is the accumulator. It is treated like a stack;
Common Lisp includes "push" and "pop" operators that are constant-time.
The only problem with this approach is that after the nested loops,
"crosses" contains the pairs in reverse order. The "nreverse" function
reverses it, producing the expected order. There is also a "reverse"
function. The difference between the two is that "nreverse" is free
to repurpose the cons cells that compose its argument, whereas "reverse"
allocates new conses for the reversed list. You should only use the
destructive "nreverse" function when you know other variables aren't
depending on parts of the list you're about to reverse, as these parts
might be rearranged out from underneath them. This is not the case in
the code above because the "crosses" list was explicitly consed by in
the nested loops (and not, for example, passed into the function as an
argument), and is obviously not shared by any other variable. Note that
this is a common idiom in Common Lisp -- consing up a list in reverse
using the efficient "push" and "pop" operators and destructively
reversing it at the end.
Note that if the crossed elements are truly pairs, then it is more
efficient (i.e., uses one fewer cons cell per pair) and perspicuous
to encode them as cons cells:
? (defun cons-cross (a b)
(let ((crosses nil))
(dolist (x a)
(dolist (y b)
(push (cons x y) crosses)))
(nreverse crosses)))
CONS-CROSS
? (cons-cross '(1 2 3) '(4 5 6))
((1 . 4) (1 . 5) (1 . 6) (2 . 4) (2 . 5) (2 . 6) (3 . 4) (3 . 5) (3 . 6))
Sashank
Shaun Jackman <········@nospam.home.com> writes:
> Kent M Pitman wrote:
>
> > Shaun Jackman <········@nospam.home.com> writes:
> >
> >> Does there exist a lisp function that has the following effect?
> >>
> >> > (cross '(1 2 3) '(4 5 6))
> >> ((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
> >
> > One way to do it is with MAPCAR and MAPCAN. That's all the help you
> > get until you say if it's homework. If it IS homework, please show a
> > sample of what you've tried so far.
>
> No, it's not home work. I'm just experimenting with lisp a bit. It seemed
> like a likely library function for a language so built around lists.
>
> This is what I tried....
> (defun cross (a b) (dolist (x a) (dolist (y b) (print `(,x ,y)))))
> It seems to be in the right direction, but I don't want to print the items,
> I want to return a list of them. I couldn't find an easy way to accomplish
> this.
Not too difficult...
(defun cross (a b)
(let ((result '()))
(dolist (x a)
(dolist (y b) (push `(,x ,y) result)))
(nreverse result)))
Of course one can think of other solutions ...
Regards
Friedrich
Shaun Jackman <········@nospam.home.com> writes:
> Kent M Pitman wrote:
>
> > Shaun Jackman <········@nospam.home.com> writes:
> >
> >> Does there exist a lisp function that has the following effect?
> >>
> >> > (cross '(1 2 3) '(4 5 6))
> >> ((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
> >
> > One way to do it is with MAPCAR and MAPCAN. That's all the help you
> > get until you say if it's homework. If it IS homework, please show a
> > sample of what you've tried so far.
>
> No, it's not home work. I'm just experimenting with lisp a bit. It seemed
> like a likely library function for a language so built around lists.
Common Lisp isn't really built around lists to that large an extent,
i.e. Lisp isn't a single-idea language. Yes lists are used for a
variety of things in Lisp, most notably its real syntax, but you can
very well write programs that make no uses of lists as datastructures
beyond that.
Vectors, arrays, and hash-tables are just as much first-class citizens
as lists are in CL.
> This is what I tried....
> (defun cross (a b) (dolist (x a) (dolist (y b) (print `(,x ,y)))))
> It seems to be in the right direction, but I don't want to print the items,
> I want to return a list of them. I couldn't find an easy way to accomplish
> this.
Others have shown you how to achieve that using dolist, and here's the
mapcan + mapcar version that Kent promised you:
(defun cross (a b)
(mapcan #'(lambda (x) (mapcar #'(lambda (y) (list x y)) b)) a))
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
Shaun Jackman wrote:
>
> Kent M Pitman wrote:
>
> > Shaun Jackman <········@nospam.home.com> writes:
> >
> >> Does there exist a lisp function that has the following effect?
> >>
> >> > (cross '(1 2 3) '(4 5 6))
> >> ((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
> >
> > One way to do it is with MAPCAR and MAPCAN. That's all the help you
> > get until you say if it's homework. If it IS homework, please show a
> > sample of what you've tried so far.
>
> No, it's not home work. I'm just experimenting with lisp a bit. It seemed
> like a likely library function for a language so built around lists.
>
> This is what I tried....
> (defun cross (a b) (dolist (x a) (dolist (y b) (print `(,x ,y)))))
^^^
--------------------------------------------------------|||
From a stylistic and readability standpoint, I've always disliked this sort of usage of backquote and comma outside of macro definitions. Is it just me? It
seems to me that (list x y) is much easier to read and obvious as to intent.
On Fri, 11 May 2001, Christopher J. Vogt wrote:
> Shaun Jackman wrote:
> > This is what I tried....
> > (defun cross (a b) (dolist (x a) (dolist (y b) (print `(,x ,y)))))
> ^^^
> --------------------------------------------------------|||
>
> From a stylistic and readability standpoint, I've always disliked this sort of usage of backquote and comma outside of macro definitions. Is it just me? It
> seems to me that (list x y) is much easier to read and obvious as to intent.
Personally, I love the shorthand provided by backquote and find that
clearer and more concise that writing out (list ...). However, if one
uses backquote all over the place one should keep in mind that one might
get bitten unexpectedly. For example, `(,a ,b c d) might expand to
(list a b 'c 'd) but it might also expand to (list* a b '(c d)), producing
an unpleasant surprise if one attempts to mutate the resulting list.
Tim
"Wolfhard Bu�" <·····@gmx.net> wrote in message ···················@buss-14250.user.cis.dfn.de...
> ·············@vanderbilt.edu (Sashank Varma) writes:
>
> > how about:
> >
> > ? (defun uncross (crosses)
> > (if (first crosses)
> > (cons (delete-duplicates (mapcar #'first crosses))
> > (uncross (mapcar #'rest crosses)))
> > nil))
>
>
> An uncross for crossed sets.
> Any idea about an uncross for crossed lists?
>
> btw
>
> (defun cross (&rest lists)
> (let ((trivials '(())))
> (if (null lists)
> trivials
> (reduce #'(lambda (a b)
> (mapcan #'(lambda (x)
> (mapcar #'(lambda (y) (cons x y)) b)) a))
> lists :from-end t :initial-value trivials))))
>
The function cross for lists has a many to one correspondence. How do you uncross
((1 1 1) (1 1 1) (1 1 1) (1 1 1) (1 1 1) (1 1 1) (1 1 1) (1 1 1)) ?
Assuming there is enough information in the crossed list to actually solve the
problem it's still tricky. I'm not sure if doing a (mapcar #'reverse crossed-lists)
at the start and then trying to collect them would help or not, but knowing the number
of lists produced and the count of different elements in each position should give a
toehold. I know I'll end up giving this more thought, thanks a lot! >:-(
lol,
Geoff
On Fri, 11 May 2001 05:44:43 GMT,
"Shaun" == Shaun Jackman <········@nospam.home.com> wrote:
Shaun> Kent M Pitman wrote:
>> Shaun Jackman <········@nospam.home.com> writes:
>>
>>> Does there exist a lisp function that has the following effect?
>>>
>>> > (cross '(1 2 3) '(4 5 6))
>>> ((1 4) (1 5) (1 6) (2 4) (2 5) (2 6) (3 4) (3 5) (3 6))
>>
>> One way to do it is with MAPCAR and MAPCAN. That's all the help you
>> get until you say if it's homework. If it IS homework, please show a
>> sample of what you've tried so far.
The solutions given only do pairwise cartesian products; higher orders would
have to be done by repeated calls. Ages ago, I hacked up a more general
thing in Emacs Lisp that does this. It also allows a predicate, to filter out
unwanted products. Cheers,
Philip
------------------------------------------------------------------------
(defun set-product (sets &optional predicate)
"Gives the cartesian product of all SETS (a list of sequences) as a list of
tuples represented as lists. Eg.: (set-product '((a b) (1 2) (x))) =>
((a 1 x) (a 2 x) (b 1) (b 2 x))
If PREDICATE (a boolean function of two args) is given, a tuple is only
extended if its last elt. and the new one satisfy PREDICATE. Thus,
(set-product '((1 2 3) (1 2 3)) '<) => ((1 2) (1 3) (2 3)), rather than
((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3)). An error is
signalled if any of the sets is empty"
;;; If there are K equal sets of size N, you get
;;; N^K tuples if predicate == nil
;;; Binomial(N,K) if predicate == '< or '>
;;; Binomial(N+K-1, K) if predicate == '<= or '>=
(if (some (lambda (x)(zerop (length x))) sets)
(error "set-product: empty set among sets"))
;;; if no common lisp package available:
;;; (if (null (catch 'empty
;;; (mapcar (lambda (x) (if (zero (length x)) (throw 'empty nil)))
;;; (cons set sets))))
;;; (error "set-product: empty set among arguments"))
(prod1
(mapcar (lambda(x) (list x)) (car sets)) ; one dim. product of first set
(cdr sets) ; rest of the sets
predicate)) ;may be nil
(defun prod1 (tuples sets pred)
;;; cartesian product of tuple list with list of other sets
;;; (interactive) ; for profiling
(if (null sets)
tuples
(prod1 (prod2 tuples (car sets) pred)
(cdr sets)
pred)))
(defun prod2 (tuples set pred) ;product tuple with set
;;; cartesian product of exactly two lists
;;; is somewhat complicated, to avoid eval-ling the predicate if there is
;;; none
;;; (interactive) ; for profiling
; (debug t)
(let* ((doit '(append e1 (list e2))) ;core of the extend function
(extend-tuple ;construct func. that extends triple
(if pred ;build in test, if there is one
(let ((lastelt (1- (length (car tuples))))) ;where to find last
`(lambda (e2) ; the test function
(if (funcall pred (elt e1 ,lastelt) ;compare with last elt
e2) ,doit nil)))
`(lambda (e2) ,doit)))) ;no test: just append
(apply
(function nconc)
(mapcar
(lambda (e1)
(delete* nil ;clear list of nil elts
(mapcar extend-tuple set)))
tuples))))
--
If you have a procedure with 10 parameters, you probably missed some. (Kraulis)
-----------------------------------------------------------------------------
Philip Lijnzaad, ········@ebi.ac.uk \ European Bioinformatics Institute,rm A2-08
+44 (0)1223 49 4639 / Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax) \ Cambridgeshire CB10 1SD, GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53