Can somebody please implement a function which computes the cartesian product of any number of lists/sets???
https://docs.python.org/3/library/itertools.html#itertools.product
>>2
in scheme pls
give me the codes
>>3
To compute the cartesian product A1x...xAn:
- if n is 0 return empty
- if n is 1 map over A1 with list
- otherwise n >= 2
-- if A1 is empty return empty
-- compute P2 as A2x...xAn
-- if P2 is empty return empty
-- combine A1 with P2 and return the result
To combine A and B, map over A with a map over B with consing A_elem with B_elem, then flatten the result with e.g. append. After this simple version works, this step can be optimized a bit.
op, fuck these guys, just google it
nobody has time to implement when you can just copy somebody else's solutions
The following is a reasonably performant implementation, but it still makes many repeat calls to the same function with the same values meaning that it would benefit massively from memoization. I have to make a sufficiently general version of memoize for this but I'll consider posting it when complete. I'm using the curried function here to avoid any sort of reverse or append of the lists.
(define (cartesian-product . An)
(let cartesian-product-iter
((values (lambda (x) x)) (An An))
(if (null? An)
(values '())
(map
(lambda (x)
(cartesian-product-iter
(lambda (y) (values (cons x y)))
(cdr An)))
(car An)))))>>8
Interestingly memoizing this function actually resulted in identical performance on all tested implementations. This must be due to some common code transformation shifting previous loop values within scope or some such thing (I've not looked into these transformations to know for sure). Needless to say this is actually exceedingly fast, I was able to calculate the cartesian product of a 5000 dimension 2000 wide set of non-repeating data on my x220 in 15 seconds in Gauche, and around 50 seconds in Chibi. Just for the sake of it I'll go ahead and post the memoized version here, but there is really no reason to use it, it's uglier, requires a helper, and depends on outside libraries. I hope these functions solve your problem sufficiently anon, I'm sorry I wasn't able to respond in a more timely manner.
(import (scheme base) (scheme hash-table) (scheme comparator))
(define (memo-cartesian-product . An)
(define table
(make-hash-table (make-default-comparator)))
(define cartesian-product-iter
(memoize
(lambda (values An)
(if (null? An)
(values '())
(map
(lambda (x)
(cartesian-product-iter
(lambda (y) (values (cons x y)))
(cdr An)))
(car An))))
(lambda (x) (cadr x))
table))
(cartesian-product-iter (lambda (x) x) An))
; a generalised memoize function based off of SICP exercise 3.27
(define (memoize function convertor table)
(lambda x
(let* ((hashable-x (convertor x))
(memoized-value (hash-table-ref table hashable-x (lambda () #f))))
(or memoized-value
(let ((result (apply function x)))
(hash-table-set! table hashable-x result)
result)))))>>9
This function is actually broken because I'm memoizing the result of evaluating the curried function as the result for every call to a sublist of An, this means it's returning the first all of the memoizing for every recomputation. The point is thus even more clear the function is of equivilent performance, ugly, wrong, and dependent on libraries, interesting stuff. (gotta look into what's actually happening here)
(use-modules (srfi srfi-1))
(define (cartesian-product . sets)
(cond
((null? sets) '(()))
(else
(let ((rest (apply cartesian-product (cdr sets))))
(append-map
(lambda (x)
(map (lambda (r) (cons x r)) rest))
(car sets))))))