Pair combinations in scheme

Question

I'm trying to find the various combinations that can be made with a list of N pairs in scheme. Here is where I'm at thus far:

(define (pair-combinations list-of-pairs)
  (if (null? list-of-pairs)
      nil
      (let ((first (caar list-of-pairs))
            (second (cadar list-of-pairs))
            (rest (pair-combinations (cdr list-of-pairs))))
        (append
            (list (cons first rest))
            (list (cons second rest))
        ))))

Now, I'm not sure if the logic is correct, but what I notice immediately is the telescoping of parentheticals. For example:

(define p1 '( (1 2) (3 4) (5 6) ))
(pair-combinations p1)
((1 (3 (5) (6)) (4 (5) (6))) (2 (3 (5) (6)) (4 (5) (6))))

Obviously this is from the repetition of the list (... within the append calls, so the result looks something like (list 1 (list 2 (list 3 .... Is there a way to do something like the above in a single function? If so, where am I going wrong, and how would it be properly done?

The answer that I'm looking to get would be:

((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))

That is, the possible ways to choose one element from N pairs.

ad absurdum · Accepted Answer · 2021-06-15T06:23:08.547

Here is one way to think about this problem. If the input is the empty list, then the result is (). If the input is a list containing a single list, then the result is just the result of mapping list over that list, i.e., (combinations '((1 2 3))) --> ((1) (2) (3)).

Otherwise the result can be formed by taking the first list in the input, and prepending each item from that list to all of the combinations found for the rest of the lists in the input. That is, (combinations '((1 2) (3 4))) can be found by prepending each element of (1 2) to each of the combinations in (combinations '((3 4))), which are ((3) (4)).

It seems natural to express this in two procedures. First, a combinations procedure:

(define (combinations xss)
  (cond ((null? xss) '())
        ((null? (cdr xss))
         (map list (car xss)))
        (else
         (prepend-each (car xss)
                       (combinations (cdr xss))))))

Now a prepend-each procedure is needed:

(define (prepend-each xs yss)
  (apply append
         (map (lambda (x)
                (map (lambda (ys)
                       (cons x ys))
                     yss))
              xs)))

Here the procedure prepend-each takes a list xs and a list of lists yss and returns the result of prepending each x in xs to the lists in yss. The inner map takes each list ys in yss and conses an x from xs onto it. Since the inner mapping produces a list of lists, and the outer mapping then produces a list of lists of lists, append is used to join the results before returning.

combinations.rkt> (combinations '((1 2) (3 4) (5 6)))
'((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))

Now that a working approach has been found, this could be converted into a single procedure:

(define (combinations-2 xss)
  (cond ((null? xss) '())
        ((null? (cdr xss))
         (map list (car xss)))
        (else
         (apply append
                (map (lambda (x)
                       (map (lambda (ys)
                              (cons x ys))
                            (combinations-2 (cdr xss))))
                     (car xss))))))

But, I would not do that since the first version in two procedures seems more clear.

It might be helpful to look just at the results of prepend-each with and without using append:

combinations.rkt> (prepend-each '(1 2) '((3 4) (5 6)))
'((1 3 4) (1 5 6) (2 3 4) (2 5 6))

Without using append:

(define (prepend-each-no-append xs yss)
  (map (lambda (x)
         (map (lambda (ys)
                (cons x ys))
              yss))
       xs))

combinations.rkt> (prepend-each-no-append '(1 2) '((3 4) (5 6)))
'(((1 3 4) (1 5 6)) ((2 3 4) (2 5 6)))

It can be seen that 1 is prepended to each list in ((3 4) (5 6)) to create a list of lists, and then 2 is prepended to each list in ((3 4) (5 6)) to create a list of lists. These results are contained in another list, since the 1 and 2 come from the outer mapping over (1 2). This is why append is used to join the results.

Some Final Refinements

Note that prepend-each returns an empty list when yss is empty, but that a list containing the elements of xs distributed among as many lists is returned when yss contains a single empty list:

combinations.rkt> (prepend-each '(1 2 3) '(()))
'((1) (2) (3))

This is the same result that we want when the input to combinations contains a single list. We can modify combinations to have a single base case: when the input is '(), then the result is (()). This will allow prepend-each to do the work previously done by (map list (car xss)), making combinations a bit more concise; the prepend-each procedure is unchanged, but I include it below for completeness anyway:

(define (combinations xss)
  (if (null? xss) '(())
      (prepend-each (car xss)
                    (combinations (cdr xss)))))

(define (prepend-each xs yss)
  (apply append
         (map (lambda (x)
                (map (lambda (ys)
                       (cons x ys))
                     yss))
              xs)))

Having made combinations more concise, I might be tempted to go ahead and write this as one procedure, after all:

(define (combinations xss)
  (if (null? xss) '(())
      (apply append
             (map (lambda (x)
                    (map (lambda (ys)
                           (cons x ys))
                         (combinations (cdr xss))))
                  (car xss)))))

Pair combinations in scheme

1 Answers1

Some Final Refinements

Linked