Генерация перестановок с использованием генераторов - PullRequest
Новая
       104

Генерация перестановок с использованием генераторов

1 голос
/ 07 июня 2019

Я писал программу для генерации всех перестановок строки: 

def print_permutations_wrapper(str):
    strList = str.split()
    print_permutations(strList, 0, len(strList))


def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        print(strList)
        return

    print_permutations(strList, start+1, end)
    for i in range(start+1, end):
        strList[start], strList[i] = strList[i], strList[start]
        print_permutations(strList, start+1, end)
        strList[i], strList[start] = strList[start], strList[i]


def main():
    str = 'a b c'
    print_permutations_wrapper(str)


if __name__ == "__main__":
    main()

Она работает правильно, но вместо того, чтобы печатать ее, я хотел ее лениво вернуть, используя yield: 

def print_permutations_wrapper(str):
    strList = str.split()
    yield from print_permutations(strList, 0, len(strList))


def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        yield strList
        return

    yield from print_permutations(strList, start+1, end)
    for i in range(start+1, end):
        strList[start], strList[i] = strList[i], strList[start]
        yield from print_permutations(strList, start+1, end)
        strList[i], strList[start] = strList[start], strList[i]


def main():
    str = 'a b c'
    x = print_permutations_wrapper(str)
    print(list(x))

if __name__ == "__main__":
    main()

Вывод, который я получаю: 

[['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c']]

, а не все перестановки.
Как это исправить?

Я использую Python 3.7.

1 Ответ

2 голосов
/ 07 июня 2019

Взяв вторую программу, но добавив print(strList), вы увидите, что функция генератора дала то, что вы ожидали, но конечный результат явно не тот, который вы ожидали.Это связано с тем, что структурированная программа берет список, но выполняет все операции с этой же копией (предполагается, что она ограничивает использование памяти).Вы также можете проверить это с помощью 

>>> strList = ['a', 'b', 'c'] 
>>> items = list(print_permutations(strList, 0, 3))
>>> items[0] is items[1]
True
>>> items[0] is strList
True

. Очевидно, что каждый отдельный элемент в items имеет тот же самый исходный strList, который был передан. Учитывая простоту проблемы, этого можно избежать, если датьвместо этого мелкая копия списка.Таким образом, соответствующая yield часть функции станет 

def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        yield list(strList)
        return

. Теперь, когда она выполняется, она должна выдавать: 

>>> strList = ['a', 'b', 'c'] 
>>> items = list(print_permutations(strList, 0, 3))
>>> items[0] is items[1]
False

Кроме того, перестановка фактически является частьюстандартная библиотека, доступная через itertools.permutation.

Связанный: "Наименьшее изумление" и изменяемый аргумент по умолчанию

...