 <p>Let's say you want to find all permutations of [1, 2, 3, 4]. There are 24 (=4!) of these, so number them 0-23. What we want is a non-recursive way to find the Nth permutation.</p> <p>Let's say we sort the permutations in increasing numerical order. Then:</p> <ul> <li>Permutations 0-5 start with 1</li> <li>Permutations 6-11 start with 2</li> <li>Permutations 12-17 start with 3</li> <li>Permutations 18-23 start with 4</li> </ul> <p>So we can get the first number of permutation N by dividing N by 6 (=3!), and rounding up.</p> <p>How do we get the next number? Look at the second numbers in permutations 0-5:</p> <ul> <li>Permutations 0-1 have second number 2.</li> <li>Permutations 2-3 have second number 3.</li> <li>Permutations 4-5 have second number 4.</li> </ul> <p>We see a similar thing with permutations 6-11:</p> <ul> <li>Permutations 6-7 have second number 1.</li> <li>Permutations 8-9 have second number 3.</li> <li>Permutations 10-11 have second number 4. </li> </ul> <p>In general, take the remainder after dividing by 6 earlier, divide that by 2 (=2!), and round up. That gives you 1, 2, or 3, and the second item is the 1st, 2nd or 3rd item left in the list (after you've taken out the first item).</p> <p>You can keep going in this way. Here's some code that does this:</p> <pre><code>from math import factorial def gen_perms(lst): all_perms = [] # Find the number of permutations. num_perms = factorial(len(lst)) for i in range(num_perms): # Generate the ith permutation. perm = [] remainder = i # Clone the list so we can remove items from it as we # add them to our permutation. items = lst[:] # Pick out each item in turn. for j in range(len(lst) - 1): # Divide the remainder at the previous step by the # next factorial down, to get the item number. divisor = factorial(len(lst) - j - 1) item_num = remainder / divisor # Add the item to the permutation, and remove it # from the list of available items. perm.append(items[item_num]) items.remove(items[item_num]) # Take the remainder for the next step. remainder = remainder % divisor # Only one item left - add it to the permutation. perm.append(items[0]) # Add the permutation to the list. all_perms.append(perm) return all_perms </code></pre>