Subsets of List Using Recursion

Question

I need to write a function that will produce all the possible subsets of a given list. I believe I should be using map, but I'm struggling to come up with the correct syntax for iterating through. Do I have to insert a lambda statement anywhere?

All possible subsets of the (list 1 2 3) should be:

(list (list) 
      (list 1) (list 2) (list 3) 
      (list 1 2) (list 2 3) (list 1 3) 
      (list 1 2 3)))

possible duplicate of [Memory efficient power set algorithm](http://stackoverflow.com/questions/7371264/memory-efficient-power-set-algorithm) , in the linked post there's an Scheme implementation — Óscar López, Oct 17 '13 at 00:32
Thank you. Looking through the answers to the power set algorithm question was really helpful. — user2888512, Oct 17 '13 at 02:19

score 0 · Answer 1 · answered Oct 17 '13 at 00:51

0

Think of generating a powerset by either including or not including each item. The base case is if you have no items, in which case the power set is a set with the empty set. Pseudo-code would be:

Powerset([]) = [[]]
Powerset(first:rest) = 
    let subPowersets = Powerset(rest) in
        [subPowerset for subPowerset in subPowersets] ++
        [first:subPowerset for subPowerset in subPowersets]

answered Oct 17 '13 at 00:51

Claudiu

224,032
165
485
680

Thank you. I get how to go about setting up the function now. – user2888512 Oct 17 '13 at 02:16

score 0 · Answer 2 · answered Oct 17 '13 at 17:40

You can also try:

(define power-set 
 (lambda (set)
   (if (empty? set) '()
        (remove-duplicates (append* (power-set (car set))
                                          (map (lambda (x) (cons (car A) x)) (power-set (cdr A))))))))

Though I use this code with other functions such as (set-union) Instead of (remove-duplicates (append*...)) Also, I sort them accordingly to their cardinality with another function.

You can construct these simple programs by reading its mathematical definition. You can improve them by reading the documentation (some mathematical definitions cause 'bad' recursion, you can try using tail-recursion)

Subsets of List Using Recursion

2 Answers2