## Python Lists and Yielding

By : Saqib
Source: Stackoverflow.com
Question!

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 square brackets, separated by commas)?

By : Saqib

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).