вывести powerset строки

Я пытаюсь написать код 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 или в моем коде есть ошибка? Я думаю, что мой код должен быть в порядке — я заканчиваю пятый выпуск интервью Cracking the coding.

Благодарю вас!


python powerset
person mythander889    schedule 28.09.2012    source источник
comment
Вы хотите сгенерировать набор мощности, а не перестановки. Единственными перестановками строки 'ab' являются 'ab' и 'ba'.   -  person Matt Ball    schedule 28.09.2012
comment
Кроме того, вам действительно не следует называть строку string (это имя встроенного модуля), и я не уверен, чего вы пытаетесь достичь, вызывая str для объектов, которые уже являются строками (first, rem, и т.д.).   -  person abarnert    schedule 28.09.2012
comment
@Matt Ball Да, хороший звонок. Тем не менее, я не генерирую «аб» или «ба». Ты знаешь почему?   -  person mythander889    schedule 28.09.2012
comment
@abarnert Совершенно верно - я переименовал строку во что-то другое и удалил лишнюю функцию str(), но все еще получаю ошибки. Есть идеи, почему?   -  person mythander889    schedule 28.09.2012
comment
Ну, очевидно, это не было причиной ваших проблем; они просто усложняли чтение… Между тем, вы должны обновить вопрос с отредактированной версией кода.   -  person abarnert    schedule 28.09.2012
comment
Я изменил название вопроса, так как ожидаемый результат - это powerset. перестановки означают что-то другое   -  person John La Rooy    schedule 28.09.2012

Ответы (6)


arrow_upward
4
arrow_downward

Вы слишком много думаете об этом

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

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

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

person John La Rooy    schedule 28.09.2012
comment
Это сделало это! Спасибо. Что делает расширение, чего не делал мой код? - person mythander889; 28.09.2012
comment
@mythander889, .extend просто загружает результат предыдущего уровня в текущий результат. - person John La Rooy; 28.09.2012
comment
Я попытался запустить этот код, он не печатает степени, он просто печатает все алфавиты строки. - person thenakulchawla; 12.10.2016
comment
@ nakulchawla09, я не уверен, что вы имеете в виду под полномочиями, но, вероятно, это отличается от набора мощности. - person John La Rooy; 13.10.2016
comment
Прошу прощения за опечатку, я имел в виду только мощность. Для этой программы я каким-то образом получал вывод [" ", "a", "b"] , я думал об условиях получения вывода типа [" ", "a", "b", "ab", "ba"] - person thenakulchawla; 13.10.2016

arrow_upward
3
arrow_downward

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

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"))
person mgilson    schedule 28.09.2012
comment
Я считаю, что это сработает, но я хочу реализовать решение с помощью рекурсии. Благодарю вас! - person mythander889; 28.09.2012
comment
искал комбинации с заменой. Увидел это, зашел в документы.. combinations_with_replacement() -- там действительно метод! :') - person Somjit; 07.11.2015
comment
Есть ли способ сделать то, что вы делаете, без использования пакета itertools? - person thenakulchawla; 12.10.2016

arrow_upward
2
arrow_downward

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

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

arrow_upward
1
arrow_downward

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

>>> 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')]
person Pedro Lacerda    schedule 28.09.2012

arrow_upward
0
arrow_downward

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

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.

(Конечно, вместо того, чтобы отслеживать это вручную, вы можете добавить еще несколько полезных операторов печати и посмотреть, что на самом деле делает каждый шаг.)

Вероятно, это был не тот алгоритм, который вам нужен, но вы должны сообщить нам, что вы пытались сделать. Вы, например, переносите какой-то псевдокод из Хоара в Python? Если да, то какой псевдокод?

person abarnert    schedule 28.09.2012

arrow_upward
0
arrow_downward

Используйте powerset из more_itertools:

>>> import more_itertools

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

Эта powerset представляет собой вспомогательную функцию, непосредственно реализованную из itertools рецептов. .

person pylang    schedule 16.12.2016