1

First off, I wanted to clarify that I understand that there are similar questions to what I am asking, but I have a very specific output case that I am trying to replicate.

I am trying to create a Scheme procedure that allows me to take a set and generate a list that shows all possible subsets of that set.

For example, if I call: (subsets '(a b c )) I should get: '((a b c) (b c) (a c) (c) (a b) (b) (a) ()) (in that order specifically)

Here is what I have so far:

(define (subsets givenList)
  (if (null? givenList)
      (list null)
      (let ((rest (subsets (cdr givenList))))
        (append rest (map (lambda (x)
                            (cons (car givenList) x))
                          rest)))))

My output for this is: (() (c) (b) (b c) (a) (a c) (a b) (a b c)) but that is not the specific output that I am looking for. Any suggestions?

ad absurdum
  • 19,498
  • 5
  • 37
  • 60
Jackscalibur
  • 39
  • 2
  • 5
    What is the logic of the required order? – Barmar Sep 17 '21 at 22:59
  • 2
    see [this answer](https://stackoverflow.com/questions/20622945/how-to-do-a-powerset-in-drracket/20623487#20623487). – Will Ness Sep 18 '21 at 20:13
  • @Barmar The order seems to be: all subsets containing `c` are first, followed by subsets containing `b` but not `c`, followed by subsets containing `a` but not `b` or `c`. Recursively, within the `c` subsets, those containing `b` are listed before those containing only `a`, and within those recursive `b` subsets, that containing `a` is listed before the one not containing `a`; there is a kind of recursive right-to-left elimination rule going on. – Kaz Sep 20 '21 at 23:31

1 Answers1

1

To obtain a list of all subsets of '(a b c), in the desired order:

  • First, as induction hypothesis, suppose that you have a list R with all subsets of '(b c) in the desired order, i.e., R = '((b c) (c) (b) ()).
  • Then, mapping each sublist of R into another sublist starting with the element a, you can create the list S = '((a b c) (a c) (a b) (a)).
  • Finally, you can interleave the elements of S and R, starting with the first element of S, to obtain the final list '((a b c) (b c) (a c) (c) (a b) (b) (a) ()).
(define (subsets L)
  (if (null? L)
      (list null)
      (let* [(R (subsets (cdr L)))
             (S (map (lambda (x) (cons (car L) x)) R))]
        (interleave S R))))

(define (interleave A B)
  (cond [(null? A) B]
        [(null? B) A]
        [else (cons (car A) (cons (car B) (interleave (cdr A) (cdr B))))]))

Example:

> (subsets '(a b c))
'((a b c) (b c) (a c) (c) (a b) (b) (a) ())
slago
  • 5,025
  • 2
  • 10
  • 23