Recursive function to calculate the powerset of a set

Question

I have been asked to write a recursive function that returns the powerset (a list of all subsets) of a set in the following exact order:

(powerset '(a b)) -> (() (b) (a) (a b))
(powerset '(a b c )) -> (() (c) (b) (b c) (a) (a c) (a b) (a b c))

We have already been asked to write a function consToAll(A L) which 'conses' A to every element of the list L. Here is my consToAll which works as it should:

(define consToAll 
    (lambda (A L)
        (cond 
            ( (null? L) '() )
            ( #t        (cons (cons A (car L)) (consToAll A (cdr L))) )
        )
    )
)

This is the closest to a working powerset function I have gotten:

(define (powerset L)
    (cond
        ( (null? L) '() )
        ( #t        (cons (powerset (cdr L)) (consToAll (car L) (powerset (cdr L)))) ) 
    )
)

which outputs:

(powerset '(a b)) -> ((()) (a))
(powerset '(a b c)) -> (((()) (b)) (a ()) (a b))

EDIT

We are also given the following hint:

"Notice that (powerset '(b) ) is '( () (b) ). Also notice that (powerset '(a b)) is made up of (powerset '(b)) appended onto (powerset '(b) ) with 'a consed onto every element."

EDIT 2

I have found the following solution in Python which appears to do what I am trying to do. I am having trouble translating the last line into Lisp, however:

def powerset(seq):
    if not seq:
        return [[]]
    ps = powerset(seq[1:])
    return ps + [[seq[0]] + n for n in ps]

Another hint: The word "appended" in the provided hint is significant. It is not the same thing as "consed". (And the "do something with every element of a list" function is called "map". You don't need to write it yourself.) — molbdnilo, Mar 10 '16 at 15:29
@molbdnilo I have come across the `map` function in other solutions, but we are specifically asked to use our `consToAll` function — KOB, Mar 10 '16 at 15:31
@molbdnilo Am I right in thinking ''(powerset '(a b)) is made up of (powerset '(b)) appended onto (powerset '(b) ) with 'a consed onto every element" can be achieved with `(cons (powerset (cdr L)) (consToAll (car L) (powerset (cdr L)))` — KOB, Mar 10 '16 at 15:34
`(cons '(1) '(2))` => `((1) 2)`. `(append '(1) '(2))` => `(1 2)`. all you need to do is change one word in your code. Python's `ps + qs` is written as `(append ps qs)` in Scheme, not `(cons ps qs)`. — Will Ness, Mar 10 '16 at 15:34
@WillNess Changing `cons` to `append` has resulted in my function always returning an empty list, I do now understand why to use append instead of cons though. — KOB, Mar 10 '16 at 15:39
ah, right, your `null?` case is wrong too. Python's `[[]]` is not `'()`. — Will Ness, Mar 10 '16 at 15:40
@WillNess I tried changing `'()` to `'(())` and for `(powerset '(a b))` I am getting `(() (a) ())` — KOB, Mar 10 '16 at 15:49
@WillNess Nevermind, I accidentally changed the `null?` case in my `consToAll` function instead of `powerset`. Thanks for the help, it works perfectly now — KOB, Mar 10 '16 at 15:50
In case you missed the reason why it didn't work, your powerset of the empty set was the empty set, but it should be the non-empty set that contains the empty set as its only member. (I hereby admit to not noticing this and looking for that bug for twenty minutes.) — molbdnilo, Mar 10 '16 at 15:55
@molbdnilo yeah, I failed to see the difference between then empty set and the set that contains the empty set until now! — KOB, Mar 10 '16 at 15:59

Recursive function to calculate the powerset of a set

0 Answers0