Генерация комбинаций строки (не перестановок) - PullRequest
Новая
       5

Генерация комбинаций строки (не перестановок)

4 голосов
/ 02 декабря 2011

Я попытался реализовать алгоритм в «Программируемых интервью» в Python, как показано ниже, но, похоже, он не работает (стр. 99 во 2-м издании):

Идея состоит в том, чтобыгенерировать все комбинации (не перестановки) строки, например, если вы введете «wxyz», вы получите «w, wx, wxy, wxyz, wxz, wy, wyz, wz ....» и т. д., если отображается wzzw недействителен. 

def doCombine(strng, out, length, level, start):
    for i in range(start, length):
        out.append(strng[i])
        print out
        if (i < length - 1):
            doCombine(strng, out, length, level +1, i + 1)
        out = out[:-1]

x = list()
target = "wxyz"
print doCombine(target, x, len(target), 0, 0)

Что здесь может быть не так?Я получаю относительно мусор.

Ответы [ 4 ]

3 голосов
/ 02 декабря 2011

В своем текущем коде попробуйте изменить строку out = out[:-1] на del out[-1].Оба эти результата приводят к удалению out последнего элемента, но в вашем текущем коде out переназначается вместо использования того же списка.Это приводит к тому, что символы никогда не удаляются из исходного списка, что, очевидно, будет довольно сильно мешать выводу.

После внесения этого изменения, вот вывод:

2 голосов
/ 02 декабря 2011

См. Функцию комбинации () из модуля itertools .

1 голос
/ 02 декабря 2011

Я переписал эту функцию объединения, используя рекурсивный генератор.Выводом является итератор. 

def combine(s):
    length = len(s)
    def gen(start, prepending=[]): #recursive generator
        if start == length-1:
            yield prepending + [s[start]]
        else:
            for i in range(start,length):
                current = prepending + [s[i]] #save the current list for reusing
                yield current
                for els in gen(i+1,current):
                    yield els
    for v in gen(0):
        yield v

s = "wxyz"
for v in combine(s):
    print(v)

Это не очень легко понять сразу.

В генераторе смешения используется та же техника: Функция соединения выполнена в функциональном стиле .

Кроме того, я немного изменил вашу функцию, пытаясь понять, как она работает.Я положу это здесь для тех, кому может быть интересно облегчить их понимание. 

def combine(s):
    out = []
    length = len(s)
    def loc(start):
        for i in range(start, length):
            out.append(s[i])
            print out
            if (i < length-1):
                loc(i+1)
            del out[-1]
    loc(0)

Я сделал несколько расчетов эффективности.

Код, которыйиспользует добавления и удаления из out (слегка измененный код исходного постера для работы в качестве генератора) немного быстрее, чем код, который я предоставил в этом ответе (я думаю, это потому, что я использовал prepending + [s[i]] на каждой итерации, которая создаетновый список в памяти. Добавления и удаления в том же списке оказываются быстрее).

Подробности здесь: https://ideone.com/V3WIM

0 голосов
/ 02 декабря 2011

Строка out.append(strng[i]) не соответствует описанному алгоритму. Вы не хотите добавлять, вы хотите установить [level] = strng [i]

...