(Схема) Рекурсивная функция для вычисления всех возможных комбинаций некоторых списков? - PullRequest
Новая
       4

(Схема) Рекурсивная функция для вычисления всех возможных комбинаций некоторых списков?

3 голосов
/ 05 апреля 2011

Что является примером рекурсивной функции для вычисления всех возможных комбинаций списков? Например, (combine (list 1 2 3) (list 1 2)) должно вернуть '((1 1) (1 2) (2 1) (2 2) (3 1) (3 2)).

Ответы [ 2 ]

3 голосов
/ 05 апреля 2011

Вот мое решение. Требуются SRFIs 1 и 26. 

(define (cartesian-product first . rest)
  (define (iter l result)
    (define (prepend-all x)
      (map (cut cons <> x) l))
    (concatenate (map prepend-all result)))
  (map reverse (fold iter (map list first) rest)))
2 голосов
/ 05 апреля 2011

Вот мой дубль;Сначала я определяю помощника concat/map, который принимает список и функцию.Как и обычный map, он применяет эту функцию к каждому элементу в списке.В отличие от map, для объединения результатов используется append, а не cons.Это полезно, потому что мы хотим вернуть один уровень списков в качестве ответа: 

(define concat/map
  (lambda (ls f)
    (cond
      [(null? ls) '()]
      [else (append (f (car ls)) (concat/map (cdr ls) f))])))

Затем написание combine для двух списков является простым.Вы берете каждый элемент первого списка, затем создаете каждый список, объединяя его и элемент x из второго списка.Так как это возвращает список ответов для каждого элемента в первом списке, используйте concat/map, чтобы собрать его вместе, как мы хотим: 

(define combine
  (lambda (xs ys)
    (concat/map xs (lambda (x)
                     (map (lambda (y) (list x y)) ys)))))

Версия combine, которая работает с одним или несколькими спискамиДавайте назовем это combine*, немного сложнее.Вместо того чтобы создавать все списки, объединяющие x с элементами из второго списка, мы просто рекурсивно запрашиваем произведение всех оставшихся ys, а затем cons x на каждый из этих результатов.Рекурсия останавливается, когда объединяются только два списка, и в этом случае используется исходный combine. 

(define combine*
  (lambda (xs . ys*)
    (cond
      [(null? ys*) (map list xs)]
      [(null? (cdr ys*)) (combine xs (car ys*))]
      [else (concat/map xs (lambda (x)
                             (map (lambda (y) (cons x y))
                                  (apply combine* ys*))))])))

В качестве бонуса, этот шаблон использования concat/map для выполнения некоторой работы и объединения полученных результатов.ответы на самом деле список монады .Здесь все упрощено, но структура на месте.

...