Python Lists and Yielding

I have the following (correct) solution to Project Euler problem 24. I'm relatively new to Python, and am stumped on a couple of Python points.

First, the code:

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

My first query is regarding the use of the yield statement. Instead of defining the permutations list at the top, my first design was to replace the permutations.append line with yield state. I would then assign the return value of the method to a variable. I checked, and the return value was a generator, as expected. However, looping over its contents indicated that no values were being generated. Am I missing something here?

My second query is about the final line - printing a value from the list. When I run this, it outputs the values as though it was a list, whereas it should be a string. In fact, replacing print(permutations[999999]) with print(type(permutations[999999])) results in < class str>. So why is it being printed like a list (with开发者_如何学Python square brackets, separated by commas)?

When you recursively call getLexicographicPermutationsOf, you need to yield results from there too.

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

permutations.append(str(state)) creates a string representation of state, which is a list. This explains why it looks like a list when printed.

There is a much less computationally intensive way to calculate this. It might actually not be so easy to write a program, but it lets you work out the answer by hand. :) (Hint: how many permutations are there? How many of them start with 0?)

Also, range(len(x)) is highly un-Pythonic. Granted, it would be nice to have the indices in order to slice the list to remove the 'current' element... but there is another way: just ask Python to remove the elements with that value (since there is only one such element). That allows us to loop over element values directly:

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 is primarily useful for actually creating data ranges - such as you initialize digits with. :)

Am I missing something here?

You're missing that just calling a function recursively won't magically put its results anywhere. In fact, even if you 'yield' the results of a recursive call, it still won't do what you want - you'll end up with a generator that returns generators (that return generators, etc.... down to the base of the recursion) when you want one generator. (FogleBird's answer explains how to deal with this: you must take the generator from the recursive call, and explicitly "feed" its yielded elements into the current generator.)

But there is a much simpler way anyway: the library already has this algorithm built in.

The entire program can be done thus:

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

why is it being printed like a list (with square brackets, separated by commas)?

Because the string contains square brackets and commas. That's what you get when you use str on a list (state, in this case).