在Scheme中生成2个列表的列表 [英] Generating list of 2-lists in Scheme

问题描述

(define cart-product
  (lambda (sos1 sos2)
    (if (null? sos1) '()
      (cons
       (cart-prod-sexpr (car sos1) sos2)
       (cart-product (cdr sos1) sos2)))))

(define cart-prod-sexpr
  (lambda (s sos)
    (if (null? sos) '()
        (cons
         (list s (car sos))
         (cart-prod-sexpr s (cdr sos))))))

呼叫(cart-product '(q w) '(x y))会产生(((q x) (q y)) ((w x) (w y))).

我该如何生产((q x) (q y) (w x) (w y))?

推荐答案

未经测试.请注意，我定义的append-list过程实际上返回一个以sos2结尾的列表.这在这里是适当的(并且是正确的做法)，但一般而言并非如此.

Untested. Note that the append-list procedure I defined actually returns a list ending in sos2. That is appropriate (and the right thing to do) here, but is not in general.

(define cart-product
  (lambda (sos1 sos2)
    (if (null? sos1) '()
      (append-list
       (cart-prod-sexpr (car sos1) sos2)
       (cart-product (cdr sos1) sos2)))))

(define cart-prod-sexpr
  (lambda (s sos)
    (if (null? sos) '()
        (cons
         (list s (car sos))
         (cart-prod-sexpr s (cdr sos))))))

(define append-list
  (lambda (sos1 sos2)
    (if (null? sos1) sos2
      (cons
        (car sos1)
        (append-list (cdr sos1) sos2)))))

请注意，如果列表的大小为n，则将花费时间O(n ³ )来生成大小为O(n ² )的列表. 使用常规append会改为使用O(n ⁴ ). 我只是在没有意识到的情况下实现了常规append.要取O(n ² )，你必须更加聪明.就像这段未经测试的代码一样.

Note that if the lists are of size n then this will take time O(n³) to produce a list of size O(n²). Using regular append would take O(n⁴) instead. I just implemented the regular append without realizing it. If you want to take O(n²) you have to be more clever. As in this untested code.

(define cart-product
  (lambda (sos1 sos2)
    (let cart-product-finish
      (lambda (list1-current list2-current answer-current)
        (if (null? list2-current)
          (if (null? list1-current)
             answer-current
             (cart-product-finish (car list1-current) sos2 answer-current))
          (cart-product-finish list1-current (car sos2)
            (cons (cons (cdr list1-current) (cdr list2-current)) answer-current))))
    (cart-product-finish list1 '() '())))

万一我有一个错误，我们的想法是递归地遍历第一个和第二个元素的所有组合，每个元素用cons替换answer-current并再加上一个其他组合，接下来已经找到了.多亏了尾部呼叫优化，这应该是有效的.

In case I have a bug, the idea is to recursively loop through all combinations of elements in the first and the second, with each one replacing answer-current with a cons with one more combination, followed by everything else we have found already. Thanks to tail-call optimization, this should be efficient.

这篇关于在Scheme中生成2个列表的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！