Декартово произведение в схеме

Question

Я пытаюсь выполнить функцию, которая возвращает декартово произведение n множеств, в Dr Scheme, множества задаются как список списков, я застрял в этом весь день, я хотел бы несколько руководств, где с чего начать.

---- ПОЗДНО ИЗМЕНИТЬ -----

Вот решение, которое я придумал, я уверен, что это не самым ЭФФЕКТИВНАЯ или аккуратным, но я только учусь схема 3 недели, так что будьте легко на меня.

Answer 1

;returs a list wich looks like ((nr l[0]) (nr l[1])......) 
    (define cart-1(λ(l nr) 
     (if (null? l) 
      l 
      (append (list (list nr (car l))) (cart-1 (cdr l) nr))))) 

;Cartesian product for 2 lists 
(define cart-2(λ(l1 l2) 
       (if(null? l2) 
      '() 
      (append (cart-1 l1 (car l2)) (cart-2 l1 (cdr l2)))))) 

;flattens a list containg sublists 
(define flatten 
(λ(from) 
(cond [(null? from) from] 
     [(list? (car from)) (append (flatten (car from)) (flatten (cdr from)))] 
     [else (cons (car from) (flatten (cdr from)))])}) 

;applys flatten to every element of l 
(define flat 
(λ(l) 
(if(null? l) 
l 
(cons (flatten (car l)) (flat (cdr l)))))) 

;computes Cartesian product for a list of lists by applying cart-2 
(define cart 
(lambda (liste aux) 
(if (null? liste) 
    aux 
    (cart (cdr liste) (cart-2 (car liste) aux))))) 


(define (cart-n l) (flat (cart (cdr l) (car l)))) 

Answer 2

;compute the list of the (x,y) for y in l 
(define (pairs x l) 
    (define (aux accu x l) 
    (if (null? l) 
     accu 
     (let ((y (car l)) 
       (tail (cdr l))) 
      (aux (cons (cons x y) accu) x tail)))) 
    (aux '() x l)) 

(define (cartesian-product l m) 
    (define (aux accu l) 
    (if (null? l) 
     accu 
     (let ((x (car l)) 
       (tail (cdr l))) 
      (aux (append (pairs x m) accu) tail)))) 
    (aux '() l)) 

Источник: Scheme/Lisp nested loops and recursion

Answer 3

Вот мое первое решение (неоптимальное):

#lang scheme 
(define (cartesian-product . lofl) 
    (define (cartOf2 l1 l2) 
    (foldl 
    (lambda (x res) 
     (append 
     (foldl 
     (lambda (y acc) (cons (cons x y) acc)) 
     '() l2) res)) 
    '() l1)) 
    (foldl cartOf2 (first lofl) (rest lofl))) 

(cartesian-product '(1 2) '(3 4) '(5 6)) 

В основном вы хотите, чтобы произвести продукт продукта списков.

Answer 4

Вот краткая реализация, которая также предназначена для минимизации размера полученной структуры в памяти, путем обмена хвостов списков компонентов. Он использует SRFI-1.

(define (cartesian-product . lists) 
    (fold-right (lambda (xs ys) 
       (append-map (lambda (x) 
           (map (lambda (y) 
            (cons x y)) 
            ys)) 
          xs)) 
       '(()) 
       lists)) 

Answer 5

Я попробовал свои силы на то, чтобы элегантное решение Марка H Weaver (https://stackoverflow.com/a/20591545/7666) легче понять.

import : srfi srfi-1 
define : cartesian-product . lists 
    define : product-of-two xs ys 
     define : cons-on-each-ys x 
      map : lambda (y) (cons x y) 
       . ys 
     append-map cons-on-each-ys 
        . xs 
    fold-right product-of-two '(()) lists 

Это по-прежнему та же логика, но именование операций.

Вышеупомянутое в wisp-syntax aka SRFI-119. Схема эквивалентной схемы равна:

(import (srfi srfi-1)) 
(define (cartesian-product . lists) 
    (define (product-of-two xs ys) 
     (define (cons-on-each-ys x) 
      (map (lambda (y) (cons x y)) 
       ys)) 
     (append-map cons-on-each-ys 
        xs)) 
    (fold-right product-of-two '(()) lists))