1

我正在尝试编写 python 代码来打印字符串的powerset，但遇到了一些错误。这是我所拥有的：

def getperm (string):
    perm = []
    if len(string) == 0:
        perm.append("")
        return perm
    #if len(string) == 1:
    #   perm.append(string)
    #   perm.append("")
    first = string[0]
    print "first = " + str(first)
    rem = string[1:len(string)]
    print "rem = " + str(rem)
    words = getperm(rem)
    for word in words:
        for i in range(len(word)):
            temp = string[0:i] + first + string[i:len(string)]
            print "temp = " + str(temp)
            perm.append(temp)

    return perm

if __name__=="__main__":
    a = "ab"
    mag  = getperm(a)
    print mag

我的预期输出是：

['', 'a', 'b', 'ab']

我的实际输出是：

[]

谁能帮我弄清楚发生了什么？这是python的一些细微差别，还是我的代码中有错误？我认为我的代码应该没问题——我要离开第五版破解编码面试

谢谢！

4

6 回答 6

4

你想多了

这部分试图做的太多

for word in words:
    for i in range(len(word)):
        temp = string[0:i] + first + string[i:len(string)]
        print "temp = " + str(temp)
        perm.append(temp)

看看它真的应该有多简单

def get_powerset (string):
    perm = []
    if len(string) == 0:
        perm.append("")
        return perm
    #if len(string) == 1:
    #   perm.append(string)
    #   perm.append("")
    first = string[0]
    print "first = " + str(first)
    rem = string[1:len(string)]
    print "rem = " + str(rem)
    words = get_powerset(rem)
    perm.extend(words)
    for word in words:
        perm.append(first+word)

    return perm

if __name__=="__main__":
    a = "ab"
    mag  = get_powerset(a)
    print mag

现在您应该能够通过一些重构使代码看起来更好

于 2012-09-28T02:08:27.730 回答
3

这是你想要的吗？

import itertools as it

def func(s):
    for i in range(len(s)+1):
        for combo in it.combinations(s,i):
            yield "".join(combo)

print list(func("abc"))
于 2012-09-28T01:38:01.667 回答
2

这是一个没有itertools模块的重构迭代解决方案：

def powerset(s):
    a = ['']
    for i,c in enumerate(s):
        for k in range(2**i):
            a.append(a[k]+c)
    return a
于 2018-07-01T00:59:41.593 回答
1

有一种排列方法：

>>> import itertools
>>> chars = "ABCD"
>>> perms = list(itertools.permutations(chars))
>>> print(perms)
[('A', 'B', 'C'),
 ('A', 'C', 'B'),
 ('B', 'A', 'C'),
 ('B', 'C', 'A'),
 ('C', 'A', 'B'),
 ('C', 'B', 'A')]
于 2012-09-28T01:43:20.310 回答
0

您是否尝试过跟踪您的算法实际上做了什么？

getperm('ab'):
  first, rem = 'a', 'b'
  words = getperm('b')
    first, rem = 'b', ''
    words = getperm('')
    words = ['']
    for word in words:
      for i in range(len(word)):
        pass # only called on '', so doesn't matter
    return []
  words = []
  for word in words:
    pass # only called on [], so doesn't matter

所以，这里没有 Python 的细微差别。您的算法在 O(N) 步骤中返回空列表，并且您已在 Python 中正确编码了该算法。

（当然，您可以添加一些更有用的打印语句，而不是手动跟踪它，并查看每个步骤实际上在做什么。）

这可能不是您想要的算法，但您需要告诉我们您想要做什么。例如，您是否正在将一些伪代码从 Hoare 移植到 Python 中？如果是这样，伪代码是什么？

于 2012-09-28T01:45:02.870 回答
0

使用powerset来自more_itertools：

>>> import more_itertools

>>> ["".join(p) for p in list(more_itertools.powerset("ab"))]
['', 'a', 'b', 'ab']

这powerset是直接从itertools 食谱中实现的便利功能。

于 2016-12-16T01:07:59.017 回答