From www@deja.com Thu Jan 11 11:51:02 2001 Message-ID: <93l3bb$m8l$1@nnrp1.deja.com> From: oleg@pobox.com Subject: cross-product of sequences X-original-Subject: Re: combinatorial stuff ?? Date: Thu, 11 Jan 2001 19:59:45 GMT Reply-To: oleg@pobox.com Newsgroups: comp.lang.scheme References: <979140319.182572766@news.uia.ac.be> X-Article-Creation-Date: Thu Jan 11 19:59:45 2001 GMT Status: OR The solution to the problem of computing a cross-product of n sequences seems especially clear if we use an append-map function, defined in SRFI-1. As the SRFI says, it's equivalent to (apply append (map f clist1 clist2 ...)) The cross-product function cross-product list-of-seqs can be easily defined recursively. To compute the cross-product of a list ((e1 e2 ...) . rest) we first need to determine (cross-product rest), which gives the list of cross-product sequences. We prepend e1, e2, ... to each of these sequences and collect the results. (define (cross-product llst) (if (null? llst) (list '()) (append-map (lambda (x) (map (lambda (prev-result) (cons x prev-result)) (cross-product (cdr llst)))) (car llst)))) (define (append-map f lst) ; See SRFI-1 (if (null? lst) lst (append (f (car lst)) (append-map f (cdr lst))))) (cross-product '((1 2) (3))) ==> ((1 3) (2 3)) (cross-product '((0) (0 1 2 3) (1 2))) ==> ((0 0 1) (0 0 2) (0 1 1) (0 1 2) (0 2 1) (0 2 2) (0 3 1) (0 3 2)) (cross-product '((1 2) (3) (4 5) (6) (7 8 9))) ==> ((1 3 4 6 7) (1 3 4 6 8) (1 3 4 6 9) (1 3 5 6 7) (1 3 5 6 8) (1 3 5 6 9) (2 3 4 6 7) (2 3 4 6 8) (2 3 4 6 9) (2 3 5 6 7) (2 3 5 6 8) (2 3 5 6 9)) Amazingly long time ago I programmed a similar problem in Algol-68. The solution turns out to involve recursion as well.