1

文字列のパワーセットを出力する Python コードを作成しようとしていますが、いくつかのバグが発生しています。これが私が持っているものです：

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 のニュアンスですか、それとも私のコードにバグがありますか? 私のコードは問題ないと思います -- Cracking thecoding インタビューの第 5 版を終了します

ありがとうございました！

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 に答える
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 で適切にコーディングしました。

(もちろん、手でトレースする代わりに、さらに便利な print ステートメントを追加して、各ステップが実際に何を行っているかを確認できます。)

それはおそらくあなたが望んでいたアルゴリズムではありませんでしたが、あなたが何をしようとしていたかを私たちに伝える必要があります. たとえば、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 に答える