Posts Tagged ‘prob24’

Problem 24 – Permutations

September 10, 2009

In problem 24 we are asked to consider the permutations of the digits 0 through 9 in lexicographic order, and then pick out a certain element of that list.

I wrote down the permutations, in order, of 0 through 2, and also 0 through 3. Looking at the list, it’s sort of easy to pick out some patterns. My first solution was to compute the desired permutation recursively, by first picking out the leading digit. For the digits 0 through 3, the first digit is 0 for (4-1)! terms, then 1 for (4-1)! terms, and so on. So we can compute the leading digit of the n-th element of the list of permutations by finding n/(4-1)! (well, the integer part). We then have one fewer elements to consider for permuting, and want the n%(4-1)!-th element of that list of permutations. Actually, this discussion assumes that the list is indexed starting at 0, so we have to be careful about that somewhere.

In code:

def factorial(n):
return reduce(lambda x,y:x*y, xrange(1,n+1), 1)

def solve(n, ar):
“”” Find the (n+1)th permutation of the elements of ar
Assumes that n >= 0, and ar[i] < ar[i+1] """ if(n == 0): return reduce(lambda s,x:s+str(x), ar, "") fact = factorial(len(ar) - 1) fidx = n // fact oidx = n % fact return str(ar[fidx]) + solve(oidx, ar[0:fidx] + ar[fidx + 1:]) [/sourcecode] This seems to be a pretty efficient solution, as we sort of expect. It has to recur no more than the number of digits you are permuting. Looking at the list of permutations of 0 through 3, it is entertaining to try to think about the algorithm to determine the next element in the list, given some chosen index. If we had such an algorithm, we could increment a counter, doing this as many times as necessary until we get up to the desired permutation. So how do we get from one element to the next? Staring at the list for a while, I came up with the following: Look at whatever string you are at, starting at the right end. Move left in this string, until the digit you are looking at is smaller than the one you just looked at. So, for example, looking at 2130 we would pick out the 1. Now consider all the digits from the 1 on, in this case 130. We need to make the next bigger number than this, from these same digits. There is a bigger number, because we know the second digit, 3, is bigger than the first, 1, so switching them would make a bigger number. But we want the smallest number bigger than the one we are looking at, 130. Find the smallest digit bigger than 1, move it to the front, and put all of the other digits afterwards, in ascending order. So we'd get 301 in the running example. With the 2 we had left out for the moment, this makes 2301 the successor of 2130. Code: [sourcecode language="python"] def solve(n, ar): tostr = lambda ar:reduce(lambda s,x:s+str(x), ar, ""); if(len(ar) == 1): return str(ar[0]) cur = 0 while(cur < n): i = len(ar) - 2 while(i>=0 and ar[i] > ar[i+1]):
i -= 1
if(i < 0): # ar is the biggest string, assume n=len(ar)!-1 return tostr(ar) # right now, ar[i] < ar[i+1], for our variable i head,tail = ar[0:i],ar[i:] nsidx, tidx = 1, 2 while(tidx < len(tail)): if(tail[tidx] > tail[0] and tail[tidx] < tail[nsidx]): nsidx = tidx tidx += 1 # tail[nsidx] is the smallest number in the tail bigger than tail[0] remtail = tail[0:nsidx] + tail[nsidx + 1:] remtail.sort() ar = head + [tail[nsidx]] + remtail cur += 1 return tostr(ar) [/sourcecode] This method is, as you should expect, slower for the stated problem. However, I started wondering about generating all of the permutations. I rearranged the two above blocks a little bit to aim for this goal. In the first version, I just did [solve(n,ar) for n in xrange(0,factorial(len(ar)))], and in the second, instead of keeping track of indices, I just stored the ar after each iteration of the loop. With these changes, the iterative script actually seems to run faster.

Advertisements