logo标签列表

递归测验 - 无法解决

pythonrecursion
11

今天我上计算机科学课时，我的教授布置了一份有关递归的Python测验。

整个班级都卡在第二题上了，以下是问题。没有人能够接近解决方案。

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

示例代码：

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]]

你只能修改下划线，就像我的示例一样。

我的解决方案离完美还很遥远，甚至不应该被考虑：

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]]

有人知道这个问题怎么解决吗？我们只有15分钟来解决，似乎是一个相当具有挑战性的问题。

仅供参考，他说他会放弃这个问题，因为班上没有人——大约10名经过精选的高级计算机科学课程的学生——能够解决它。

这似乎是一个问题，要生成长度为1..n的列表的所有排列 - 但是查看其他解决方案，它们似乎都不是这种形式。问题可能是错误的。 - Waleed Khan
2
@WaleedKhan：示例代码非常清楚地表明，sub_set 应该返回给定列表的所有“子集”列表，而不是排列。如果是排列，那么 [2,1,3] 和 [3,2,1]（以及其他一些）将会出现在 sub_set([1,2,3]) 的输出中，除了 [1,2,3]。 - jwodder
7个回答
14

我认为这个问题有一个漏洞。递归的基本情况是错误的。

空集的所有子集的集合不是空集，而是包含空集的集合。

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

应该是

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

新增: 根据该补丁，这里是一个解决方案：

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
1
在苦思冥想了20多分钟之后，我相信你是对的。 - Christian Ternus
我开始怀疑这可能是一个恶作剧问题，而学生们需要找出基本情况是错误的（15分钟内应该可以做到）... 无论如何，noa获得了班级额外学分;问题是教授是否会得到F。 :) - abarnert
嘿嘿，听起来大概没错。需要15分钟才能意识到基本情况有错，还需要另外20分钟才能了解+对Python列表的影响。 - paulmelnikow
@noa：但是+对于一个列表并没有任何作用，除非另一个操作数有一个可以改变other的__radd__(self, other)方法。 :) （我知道你的意思，只是在开玩笑。） - abarnert
非常感谢。我已经和他提起过了，确实是这种情况。这只是代码中的一个错误。 - Obicere
3
我认为这个问题很难在不进行大规模的修改的情况下得到解决，因为基本情况是错误的。对于 []，应该有一个子集: 即 [] 本身。但是 return A 返回了没有 子集。
所以，你需要做的不仅仅是执行 A[:1] + L，而是要执行 [A[:1] + L]。此外，你还需要执行 [A[:1]] + X + result 而不是 A[:1] + X + result。因此代码如下：
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

这仍然使得空列表在子集中被排除。唯一解决这个问题的方法就是像这样做一些愚蠢的事情:

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

这将至少返回正确的值...但顺序错误，并且所有单个元素子集都有重复。如果您想进一步扩展hackiness，可以这样做；但我认为这不值得。
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]]
不包括[]，也不按指定顺序。 - Christian Ternus
嗯，你说得对，我没有注意到[]应该在那里。不确定顺序是否重要。 - Brionius
已经修正了顺序，但不确定如何将空集合放入其中。 - Brionius
如果你忽略了原问题中的错误，那么你是正确的。+1。 - Christian Ternus
在最后一次编辑之后，这与我在Scott Hunter的答案中的评论完全相同，因此出于与我的评论相同的原因是错误的。 - abarnert
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]]

这基本上与noa's的答案相同，只是不包括您不应编辑的代码部分。
只是一个建议。与其仅仅发布代码，如果能够添加解释说明，对于提问者会更有帮助 :) - Harry
0

虽然这不是你寻找的解决方案，但以下是一个使用yield的可行解决方案 :)

def powerset(A):
    if A:
        for L in powerset(A[1:]):
            yield L
            yield A[:1] + L
    else:
        yield []
2
如果你要回答一个不同的问题，为什么不直接 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))？ - abarnert
我刚刚意识到我所输入的内容与itertools中的powerset在字符上完全相同。所以，我想我比我想象中聪明得少了一些，但这甚至比我想象中的“显而易见的方法”更加明显。 :) - abarnert
@abarnert：只是因为我觉得这个版本稍微容易阅读一些 :) 但是没有什么阻止你将其发布为答案 ;) - Wolph
读起来更容易的是 return more_itertools.powerset(A)。 :) - abarnert
0

这里有一个可能的解决方案。它返回正确的值，但不一定按相同的顺序：

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]])

实际上，这个程序的作用是对于每一层，我们将原始列表分成两部分：初始项和剩余的列表。我们获取剩余列表的所有子集，将第一项附加到每个子集中，添加一个[]，然后返回它。

示例流程：

[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]]

一般的流程是 [] + A0*[子集] + [子集]。需要注意的问题是，子集本身总是以 [] 开头 - 所以如果不移除它，你会得到两次。还要确保在已经存在 A0 的情况下不重复添加它（因为 [A0] + [] == [A0]，而且列表中始终包含 [A0]），但在第一次迭代之后（返回 [] 后），你必须特别包含它。

0

X 是所有不包含 A[0] 的子集的集合。这意味着它们也属于 subset(A)。缺少的是所有包含 A[0] 的子集，你可以通过将 A[0] 添加到 X 中的每个元素来获得。

因此，你的第一个空白应该是 A[0] + L

而你的第二个空白应该是 result + X

对于任何输入都返回[]。试试看。 - abarnert
如果你将它改为[[A[0]] + L]，那会更接近......但是你还需要在第二个空格中添加[[A[0]]]。而且你仍然无法在结果中获得空列表。 - abarnert
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接