11

今天我的 CPSC 教授布置了一个 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 名精心挑选的学生组成的高级计算机科学班 - 可以解决这个问题。

4

7 回答 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
于 2013-10-18T01:09:21.017 回答
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；我不认为这是值得的。

于 2013-10-18T01:11:44.873 回答
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]]
于 2013-10-18T01:10:45.793 回答
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 的答案基本相同，减去对您不应该编辑的代码部分的更改。

于 2013-10-18T01:55:13.793 回答
0

X是不包括的所有子集的集合A[0]。这意味着他们也在subset(A). 缺少的是 DO 包含的所有子集，您A[0]可以通过将.A[0]X

所以你的第一个空白将是A[0] + L

你的第二个是result + X

于 2013-10-18T00:58:35.557 回答
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*[subset] + [subset]。需要注意的问题是子集本身总是以 [] 开头 - 所以如果你不删除它，你会得到它两次，并确保当它已经存在时你不会复制 A0（如 [A0] + [] == [A0]，并且列表中总是有 [A0]），但是在第一次迭代时（返回 [] 之后），您必须特别包含它。

于 2013-10-18T12:53:45.577 回答
0

不是您正在寻找的解决方案，但这是一个使用 yield 的工作解决方案:)

def powerset(A):
    if A:
        for L in powerset(A[1:]):
            yield L
            yield A[:1] + L
    else:
        yield []
于 2013-10-18T01:09:23.167 回答