1 
(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))ますか？

4

5 に答える 5

4

勝つための高階関数。より良い解決策として、Haskell のリスト内包表記を Scheme に変換しました。

; cart xs ys = [ [x,y] | x <- xs, y <- ys ]
(define (cart xs ys)
  (let ((f (lambda (x) (map (lambda (y) (list x y)) ys))))
    (concatenate (map f xs))))

(cart '(a b c) '(x y)) => ((a x) (a y) (b x) (b y) (c x) (c y))

m*n (m = |xs|, n = |ys|) で実行されます。concatenate は SRFI-1 からのものです。

于 2011-02-20T21:17:55.967 に答える
2

頭のてっぺんから：

(define cart-product
  (lambda (sos1 sos2)
    (if (null? sos1) 
        '()
        (append
         (cart-prod-sexpr (car sos1) sos2)
         (cart-product (cdr sos1) sos2)))))
于 2011-02-20T16:29:55.690 に答える
2

未テスト。append-list私が定義したプロシージャは、実際には で終わるリストを返すことに注意してくださいsos2。ここではそれが適切 (そして正しいこと) ですが、一般的にはそうではありません。

(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 2 )のリストを生成するにはO(n 3 ) の時間がかかることに注意してください。 通常を使用すると、代わりに O(n 4 ) が必要になります。気づかずにレギュラーを実装しただけです。O(n 2 ) を取得したい場合は、より賢くする必要があります。このテストされていないコードのように。append append

(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 '() '())))

バグがある場合に備えて、1 番目と 2 番目の要素のすべての組み合わせを再帰的にループし、それぞれanswer-currentを aconsに置き換えて、もう 1 つの組み合わせを使用し、その後に既に見つかった他のすべての要素が続くようにします。テールコール最適化のおかげで、これは効率的です。

于 2011-02-20T16:20:56.543 に答える
1 
(reduce #'append 
           (mapcar #'(lambda(x)
                         (mapcar #'(lambda(y) 
                                       (list x y))
                          '(a b c))) 
           '(1 2 3)))

=>((1 A) (1 B) (1 C) (2 A) (2 B) (2 C) (3 A) (3 B) (3 C))

[注: 解決策は Common Lisp (CLisp) であり、Scheme ではありませんが、Scheme でも非常に似ているはずです]

外側の (reduce #'append ) は、knivil によるソリューションで与えられた (concatenate (map ) を置き換えるためのものです

ただし、他のソリューションと比較して、私のソリューションがパフォーマンス パラメータでどのように積み上げられているかはわかりません。誰かがそれについてコメントしてもらえますか?

于 2011-09-23T18:24:49.113 に答える
1

これは、同じ問題に対する異なる解決策です。これは理解しやすく、誰かの役に立つかもしれないと思います。

(define (cart-product l1 l2)
  (define (cart-product-helper l1 l2 org_l2)
    (cond
      ((and (null? l1)) `())
      ((null? l2) (cart-product-helper (cdr l1) org_l2 org_l2))
      (else (cons (cons (car l1) (car l2)) (cart-product-helper l1 (cdr l2) org_l2)))
    )
  )
  (cart-product-helper l1 l2 l2)
)
于 2014-08-21T20:59:45.443 に答える