Списки Python и выход

Question

У меня есть следующее (правильное) решение проблемы Project Euler 24. Я относительно новичок в Python и нахожусь в тупике на нескольких точках Python.

Во-первых, код:

# A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4.
# If all of the permutations are listed numerically or alphabetically, we call it lexicographic order.
# The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210
# What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

permutations = []

def getLexicographicPermutationsOf(digits, state):
    if len(digits) == 0:
        permutations.append(str(state))

    for i in range(len(digits)):
        state.append(digits[i])
        rest = digits[:i] + digits[i+1:]
        getLexicographicPermutationsOf(rest, state)
        state.pop()

digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
getLexicographicPermutationsOf(digits, [])
print(permutations[999999])

Мой первый запрос касается использования оператора yield.Вместо того, чтобы определять список перестановок в верхней части, мой первый дизайн должен был заменить строку permutations.append на yield state.Затем я бы присвоил возвращаемое значение метода переменной.Я проверил, и возвращаемое значение было генератором, как и ожидалось.Однако цикл по его содержимому показал, что никакие значения не генерируются.Я что-то здесь упускаю?

Мой второй запрос о последней строке - вывод значения из списка.Когда я запускаю это, он выводит значения, как если бы это был список, тогда как это должна быть строка.Фактически, замена print(permutations[999999]) на print(type(permutations[999999])) приводит к < class str>.Так почему же он печатается как список (в квадратных скобках, разделенных запятыми)?

Answer 1

Когда вы рекурсивно вызываете getLexicographicPermutationsOf, вам также нужно получить оттуда результаты.

for result in getLexicographicPermutationsOf(rest, state):
    yield result

permutations.append(str(state)) создает строковое представление state, которое является списком.Это объясняет, почему при печати оно выглядит как список.

Answer 2

Существует гораздо менее сложный способ вычисления этого. На самом деле написать программу может быть не так просто, но она позволяет вам выработать ответ вручную. :) (Подсказка: сколько существует перестановок? Сколько из них начинается с 0?)

Кроме того, range(len(x)) крайне непифоничен. Конечно, было бы неплохо иметь индексы, чтобы разрезать список, чтобы удалить «текущий» элемент ... но есть и другой способ: просто попросите Python удалить элементы с этим значением (поскольку существует только один такой элемент ). Это позволяет нам зацикливать значения элементов напрямую:

for digit in digits:
    state.append(digit)
    rest = digits[:]
    rest.remove(digit) # a copy with the current value removed.
    getLexicographicPermutationsOf(rest, state)
    state.pop()

range в первую очередь полезен для фактического создания диапазонов данных, например, при инициализации digits с помощью. :)

Я что-то здесь упускаю?

Вам не хватает того, что простой рекурсивный вызов функции никуда не волшебно поместит ее результаты. На самом деле, даже если вы «дадите» результаты рекурсивного вызова, он все равно не будет делать то, что вы хотите - вы получите генератор, который возвращает генераторы (которые возвращают генераторы и т. Д.) Вплоть до база рекурсии), когда вы хотите один генератор. (Ответ FogleBird объясняет, как с этим справиться: вы должны взять генератор из рекурсивного вызова и явно «подать» его полученные элементы в текущий генератор.)

Но в любом случае есть гораздо более простой способ: в библиотеку уже встроен этот алгоритм.

Вся программа может быть выполнена таким образом:

from itertools import permutations, islice
print next(islice(permutations(range(10)), 1000000, None))

почему он печатается как список (в квадратных скобках, разделенных запятыми)?

Потому что строка содержит квадратные скобки и запятые. Это то, что вы получаете, когда используете str в списке (state, в данном случае).