Печать powerset строки

Question

Я пытаюсь написать код Python для печати /tags/powerset/info строки, но сталкиваюсь с некоторыми ошибками. Вот что у меня есть:

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 the coding

Спасибо!

Answer 1

Вы переосмысливаете это

Эта часть пытается сделать слишком много

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

Теперь вы сможете сделать код более приятным с небольшим рефакторингом.

Answer 2

Это то, что вы хотите?

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

Answer 3

Вот реорганизованное итеративное решение без itertools модуль:

def powerset(s):
    a = ['']
    for i,c in enumerate(s):
        for k in range(2**i):
            a.append(a[k]+c)
    return a

Answer 4

Есть метод для перестановок:

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

Answer 5

Использование powerset от more_itertools:

>>> import more_itertools

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

это powerset это удобная функция, непосредственно реализованная из itertools рецепты.

Answer 6

Вы пробовали проследить, что на самом деле делает ваш алгоритм?

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? Если так, что за псевдокод?