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

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

---- LATER EDIT -----

Вот решение, с которым я столкнулся, я уверен, что он не самый эффективный или опрятный, но я занимаюсь только схемой в течение 3 недель, поэтому будьте легко на меня.

Ответы

Ответ 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))))

Ответ 2

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

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

Ответ 3

;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))

Источник: Схема / Lisp вложенные циклы и рекурсия

Ответ 4

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

#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))

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

Ответ 5

Я попытался понять, как элегантное решение Mark H Weaver (fooobar.com/info/6933/...) легче понять.

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, а также 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))