Recursion Quiz - Couldn't Solve

Question

Today my CPSC professor assigned a quiz in python, the topic was recursion.

The whole class got stuck on question number two, which is below. Nobody was able to even come close to a solution.

def sub_set(A):
    if A == []: return A
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += _____
    return _____

Example code:

print(sub_set([1, 2]))    # [[], [1], [2], [1, 2]]
print(sub_set([1, 2, 3])) # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

You are only allowed to modify the underscores, such as my example below may demonstrate.

My solution was so far from close, it really shouldn't even be considered:

def sub_set(A):
    if A == []: return A
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += _____
    return result + [A[:1]] + [A] + [A[::2]]

#sub_set([1, 2, 3]) -> [[3], [3], [3], [2], [2, 3], [2], [1], [1, 2, 3], [1, 3]]

Does anyone know how this could be solved? It seems like quite a challenging problem when we have only 15 minutes to solve it.

Just for reference, he said he would drop the question considering nobody in the class - advanced comp sci class of about 10 carefully selected students - could solve it.

This seems to be a problem to generate all permutations of length 1..n of a list — but looking at [other solutions](http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python), none of them seem to be in the form. The question is probably wrong. — Waleed Khan, Oct 18 '13 at 01:09
@WaleedKhan: The example code makes it quite clear that `sub_set` is supposed to return a list of all "subsets" of the given list, not permutations. If it were permutations, `[2,1,3]` and `[3,2,1]` (among others) would be in the output from `sub_set([1,2,3])` in addition to `[1,2,3]`. — jwodder, Oct 18 '13 at 01:15

paulmelnikow · Accepted Answer · 2013-10-18T01:31:33.070

14

I think there's a bug in the question. The base case for the recursion is wrong.

The set of all subsets of an empty set is not the empty set, but rather, the set containing the empty set.

def sub_set(A):
    if A == []: return A

should be

def sub_set(A):
    if A == []: return [A]

Added: With that patch, here's a solution:

def sub_set(A):
    if A == []: return [A]
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += [L, A[0:1] + L]
    return result

edited Oct 18 '13 at 01:31

answered Oct 18 '13 at 01:09

paulmelnikow

16,895
8
63
114

1

After banging my head against it for 20-odd minutes, I'm convinced you're right. – Christian Ternus Oct 18 '13 at 01:12
I'm starting to wonder if maybe this was a trick question, and the point was for the students to figure out that the base case is wrong (which should be doable in 15 minutes)… Either way, noa gets the extra credit for the class; the question is whether the professor gets an F or not. :) – abarnert Oct 18 '13 at 01:29
Haha, sounds about right. 15 minutes to realize the base case is wrong, and another 20 to learn what `+` does to a Python list. – paulmelnikow Oct 18 '13 at 01:34
@noa: But `+` doesn't do anything to a list, unless the other operand has an `__radd__(self, other)` method that mutates `other`. :) (I know what you mean, just being silly.) – abarnert Oct 18 '13 at 01:40
Thank you so much. I brought this up with him and this was indeed the case. It was just a bug in the code. – Obicere Oct 18 '13 at 13:33

score 3 · Answer 2 · answered Oct 18 '13 at 01:11

I don't believe this is solvable without some major hackery, because the base case is wrong. For [], there should be one subset: [] itself. But return A returns no subsets.

So, instead of just doing A[:1] + L, you need to do [A[:1] + L]. And, instead of A[:1] + X + result, you have to do [A[:1]] + X + result. So:

def sub_set(A):
    if A == []: return A
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += [A[:1] + L]
    return [A[:1]] + X + result

This still leaves the empty list out of the subsets for anything. And the only way to fix that is something stupid like this:

    return ([] if [] in X + result else [[]]) + [A[:1]] + X + result

This will at least return the right values… but in the wrong order, and with duplicates of all one-element subsets. You can extend the hackiness further if you want; I don't think it's worth it.

Brionius · Answer 3 · 2013-10-18T01:16:04.143

2

def sub_set(A):
    if A == []: return A
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += [L, [A[0]]+L]
    return [[A[0]]] + result

print sub_set([1, 2])
>> [[1], [2], [1, 2]]
print sub_set([1, 2, 3])
>> [[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

edited Oct 18 '13 at 01:16

answered Oct 18 '13 at 01:10

Brionius

13,858
3
38
49

Doesn't include `[]`, and isn't in the order specified. – Christian Ternus Oct 18 '13 at 01:11
Hmm, you're right, didn't notice that the `[]` was supposed to be in there. Not sure if the order is supposed to matter, though. – Brionius Oct 18 '13 at 01:13
Fixed the order, but not sure how to get the empty set in there. – Brionius Oct 18 '13 at 01:16
If you ignore the bug in the original question, you're correct. +1. – Christian Ternus Oct 18 '13 at 01:17
After the last edit, this is exactly the same as my comment on Scott Hunter's answer, and therefore is wrong for the same reasons my comment was wrong. – abarnert Oct 18 '13 at 01:19

score 1 · Answer 4 · edited May 23 '17 at 11:58

1

def sub_set(A):
    if A == []: return A
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += [L, A[0:1] + L]
    return result if X != [] else [[], A[0:1]]

This is essentially the same as noa's answer, minus the change to the part of the code you're not supposed to edit.

edited May 23 '17 at 11:58

Community

1
1

answered Oct 18 '13 at 01:55

dlongley

2,078
14
17

Just a suggestion. Rather than just posting the code, it would be more helpful for the OP if an explanation is added to it :) – Harry Oct 18 '13 at 02:16

score 0 · Answer 5 · answered Oct 18 '13 at 00:58

0

X is the set of all subsets that DON'T include A[0]. This means that they are also in subset(A). What's missing is all the subsets that DO contain A[0], which you can get by adding A[0] to each of the elements in X.

So your first blank would be A[0] + L

And your second would be result + X

answered Oct 18 '13 at 00:58

Scott Hunter

48,888
12
60
101

That returns `[]` for any input. Try it. – abarnert Oct 18 '13 at 00:59
If you changed it to `[[A[0]] + L]`, that would be closer… but then you'd need to also add `[[A[0]]]` to the second blank. And you still wouldn't get the empty list in your results. – abarnert Oct 18 '13 at 01:06

score 0 · Answer 6 · answered Oct 18 '13 at 01:09

0

Not the solution you are looking for, but here's a working solution using yield :)

def powerset(A):
    if A:
        for L in powerset(A[1:]):
            yield L
            yield A[:1] + L
    else:
        yield []

answered Oct 18 '13 at 01:09

Wolph

78,177
11
137
148

2

If you're going to answer a different question, why not just `return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))`? – abarnert Oct 18 '13 at 01:17
I just realized that what I typed is character-for-character identical to `powerset` in the `itertools` [recipes](http://docs.python.org/2/library/itertools.html#recipes). So, I guess I'm less clever than I thought, but it's even more the "obvious way to do it" than I thought. :) – abarnert Oct 18 '13 at 01:21
@abarnert: simply because I find this version slightly easier to read :) But nothing is stopping you from posting that as an answer ;) – Wolph Oct 18 '13 at 01:28
Well, it's even easier to read `return more_itertools.powerset(A)`. :) – abarnert Oct 18 '13 at 01:38

score 0 · Answer 7 · answered Oct 18 '13 at 12:53

here is a possible solution. it returns the right values, but not necessarily in the same order:

def sub_set(A):
    if A == []: return A
    X = sub_set(A[1:])
    result = []
    for L in X:
        result += [ A[:1] +L ]
    return [[]] + X[1:] + (result or [A[:1]])

Effectively what this is doing, is for each layer, we split the original list into two parts: the initial item, and the rest of the list. We get all subsets of the rest of the list, append the first item to each piece, prepend a [], and return it.

Example flow:

[1,2,3] -> A0 = [1], A1X =[2,3] ->
    [2,3] -> A0 = [2], A1X = [3] ->
        [3] -> A0 = [3], A1X = [] ->
            [] -> return []
        [3] * [] = []. return [ [], [3] ]
    [2] * [[], [3]] = [[2], [2,3]]. return [ [] + [[3]] + [[2], [2,3]] ]
[1] * [ [], [3], [2], [2,3] ] = [[1], [1,3], [1,2], [1, 2, 3] ]
             return [ [] + [[], [3], [2], [2,3]] + [[1], [1,3], [1,2], [1,2,3]]

General flow is [] + A0*[subset] + [subset]. Issues to watch are that subset itself always starts with [] - so you'll get it twice if you don't remove it, and to make sure you don't duplicate A0 when it's already there (as [A0] + [] == [A0], and you always have [A0] in the list), but on the very first iteration (after returning []) you have to specially include it.

Recursion Quiz - Couldn't Solve

7 Answers7