Is there a built-in way (or an easy way) to do something like:
(combo-list '(a b) '(c d)) -> ((a c) (a d) (b c) (b d))
Or at the most:
(combo-list '(a b) '(c d) '(e f)) -> ((a c e) (a c f) (a d e) (a d f)
(b c e) (b c f) (b d e) (b d f))
Ideally, I'd like the order to reflect picking first from the first
list, then from the second, and lastly from the third.
Basically, making combos of lists, taking one element from each list
and combing them into a new list.
Thanks!
··········@gmail.com (methodmano) writes:
> Is there a built-in way (or an easy way) to do something like:
>
> (combo-list '(a b) '(c d)) -> ((a c) (a d) (b c) (b d))
>
> Or at the most:
>
> (combo-list '(a b) '(c d) '(e f)) -> ((a c e) (a c f) (a d e) (a d f)
> (b c e) (b c f) (b d e) (b d f))
>
> Ideally, I'd like the order to reflect picking first from the first
> list, then from the second, and lastly from the third.
>
> Basically, making combos of lists, taking one element from each list
> and combing them into a new list.
>
> Thanks!
(DEFUN COMBINE (&REST ARGS)
"
RETURN: (elt args 0) x (elt args 1) x ... x (elt args (1- (length args)))
= the set of tuples built taking one item in order from each list
in args.
EXAMPLE: (COMBINE '(WWW FTP) '(EXA) '(COM ORG)))
--> ((WWW EXA COM) (WWW EXA ORG) (FTP EXA COM) (FTP EXA ORG))
"
(COND
((NULL ARGS) '(NIL))
((NULL (CAR ARGS)) (APPLY (FUNCTION COMBINE) (CDR ARGS)))
((CONSP (CAR ARGS))
(MAPCAN (LAMBDA (ITEM) (APPLY (FUNCTION COMBINE) ITEM (CDR ARGS)))
(CAR ARGS)))
(T
(MAPCAN (LAMBDA (REST) (LIST (CONS (CAR ARGS) REST)))
(APPLY (FUNCTION COMBINE) (CDR ARGS))))));;COMBINE
--
__Pascal Bourguignon__ http://www.informatimago.com/
Voting Democrat or Republican is like choosing a cabin in the Titanic.
··········@gmail.com (methodmano) writes:
> Is there a built-in way (or an easy way) to do something like:
>
> (combo-list '(a b) '(c d)) -> ((a c) (a d) (b c) (b d))
There is no built-in way, but implementing this doesn't require
much code. I wrote it as a recursive function with two loops in
7 lines and 11 pairs of parentheses.
methodmano wrote:
> Is there a built-in way (or an easy way) to do something like:
>
> (combo-list '(a b) '(c d)) -> ((a c) (a d) (b c) (b d))
>
> Or at the most:
>
> (combo-list '(a b) '(c d) '(e f)) -> ((a c e) (a c f) (a d e) (a d f)
> (b c e) (b c f) (b d e) (b d f))
>
> Ideally, I'd like the order to reflect picking first from the first
> list, then from the second, and lastly from the third.
>
> Basically, making combos of lists, taking one element from each list
> and combing them into a new list.
>
> Thanks!
You are trying to compute the Cartesian product. Assuming the inputs are
a number of sets (in principle unordered) you wind up with a set of
ordered n-tuples:
(defun cartesian-product (&rest sets)
(cartesian-product-aux sets))
;;;
;;; Use of auxilliary function here avoids need for APPLY with each
;;; recursive call since we have &REST param above.
;;;
(defun cartesian-product-aux (sets)
(if (null sets)
(list '())
(spread-layer (first sets)
(cartesian-product-aux (rest sets)))) )
;;;
;;; (spread-layer '(c d) '((e) (f))) => ((C E) (C F) (D E) (D F))
;;;
(defun spread-layer (src dest)
"Distribute each element of SRC over each sublist in DEST."
(if (null src)
'()
(spread-elt (first src)
dest
(spread-layer (rest src) dest))))
;;;
;;; (spread-elt 'd '((e) (f)) '()) => ((D E) (D F))
;;; (spread-elt 'c '((e) (f)) '((D E) (D F))) => ((C E) (C F) (D E)
(D F))
;;;
(defun spread-elt (elt partial result)
"Distribute a single element over each sublist in PARTIAL, adding
these results to RESULT."
(if (null partial)
result
(cons (cons elt (first partial))
(spread-elt elt (rest partial) result))))
methodmano asked:
> Is there a built-in way (or an easy way) to do something like:
>
> (combo-list '(a b) '(c d)) -> ((a c) (a d) (b c) (b d))
>
> Or at the most:
>
> (combo-list '(a b) '(c d) '(e f)) -> ((a c e) (a c f) (a d e) (a d f)
> (b c e) (b c f) (b d e) (b d f))
It is nearly very easy. Write a two argument version like
this:
(defun two-arg-cart-prod (s1 s2)
(let (accumulator)
(dolist (x (reverse s1))
(dolist (y (reverse s2))
(push (list x y)
accumulator)))
accumulator))
then turn it into an n argument version with reduce:
(defun pedantic-cart-prod (&rest list-of-sets)
(reduce (function two-arg-cart-prod)
list-of-sets))
(pedantic-cart-prod '(a b) '(1 2) '(x y))
=> (((A 1) X) ((A 1) Y) ((A 2) X) ((A 2) Y)
((B 1) X) ((B 1) Y) ((B 2) X) ((B 2) Y))
Close, but the distinction between a duple, one of whose
components is a duple, and a triple, is less than useful
here.
So let us rewrite two-arg-cart-prod to use CONS instead of
LIST
(defun two-arg-cart-prod (s1 s2)
(let (accumulator)
(dolist (x (reverse s1))
(dolist (y (reverse s2))
(push (cons x y)
accumulator)))
accumulator))
(two-arg-cart-prod '(1 2) '(a b))
=> ((1 . A) (1 . B) (2 . A) (2 . B))
and rather conveniently
(two-arg-cart-prod '(1 2 3) '( nil )) => ((1) (2) (3))
so, with a little care over direction and initial values we
can write
(defun cart-prod (&rest list-of-sets)
(reduce (function two-arg-cart-prod)
list-of-sets
:from-end t
:initial-value '( nil ) ))
(cart-prod '(a b) '(1 2) '(x y))
=> ((A 1 X) (A 1 Y) (A 2 X) (A 2 Y)
(B 1 X) (B 1 Y) (B 2 X) (B 2 Y))
Alan Crowe
Edinburgh
Scotland
* methodmano writes:
> Is there a built-in way (or an easy way) to do something like:
>
> (combo-list '(a b) '(c d)) -> ((a c) (a d) (b c) (b d))
(defun cross (&rest lists)
(reduce (lambda (list crosses)
(mapcan (lambda (item)
(mapcar (lambda (cross) (cons item cross)) crosses))
list))
lists :from-end t :initial-value '(())))
(defun uncross (cross)
(mapcar #'remove-duplicates (zip cross)))
How about an efficient uncross?
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)