Small Programming Challenge no. 5 – Generating a Permutation
I thought of this one quite a long time ago, and I believe that the idea behind it is pretty nice mathematically. I got the idea for it from Knuth’s “The Art of Computer Programming”.
The challenge is simple:
write a function that receives as arguments two numbers, n, and num such that 0 <= num < n!. This function needs to return an array (list) representing a permutation of the numbers 0..n-1. For each possible num, the function needs to return a different permutation, such that over all values of num, all possible permutations are generated. The order of permutations is up to you.
The function you write should do this in at most O(n) time & space (Various O(nlogn) are also acceptable).
Write your solutions in the comments, in [ LANG ] [/ LANG ] blocks (without the spaces) where LANG is preferably Python :). I will post my solution in a few days. As usual, the most efficient & elegant solution wins.
Go!
Tags: challenge, Programming
November 11th, 2009 at 2:19 pm
options = range(1,n+1)
retval = []
while (n>0):
d = num % n
num = num / n
val = options[d-1]
retval.append(val)
options.remove(val)
n = n-1
return retval
use some better data structure (hashed linklist) for options to get the remove(val) in O(1)
November 11th, 2009 at 3:00 pm
At first I thought it was easy ...
At the end I've got to the same solution as Goldy, using lists, and at every step determining one more item towards the end. It's ugly and non-pythonic, I know:
""" imri's challenge http://bit.ly/28OYz1 """
permutation = range(0, n)
factorial = reduce(lambda a,b:a*b,range(1,n+1))
for i in range(n,0,-1):
factorial = factorial / i
target = num / factorial
num = num % factorial
permutation[i-1], permutation[i-target-1] = permutation[i-target-1], permutation[i-1]
return permutation
November 12th, 2009 at 5:25 am
I love challenges !!
here is my shot
index , perm =range(n) , [None]*n
for i in range(n):
p = m%(n-i)
perm[ index[p] ]=i
del index[p]
return perm
I didn't have time to study it's speed.
It's almost the same alg as goldy (the idea to do m%i ), except that the introduction of the "index" array.
I guess it is possible to use previously computed modulos to perform new ones:
if I've calculated p[4] = m%4, then p[2] = p[4]%2 witch is must faster... but I don't think it will increase the global speed ...
November 12th, 2009 at 8:31 am
"""Remove a value from the list without maintaining order.
Running time is O(1)
"
""def extract(self, index):
value = self[index]
self[index] = self[len(self) - 1]
self.pop()
return value
def permute(n,num):
"""Modified goldy's solution to use the new class
"""
options = Options(range(1, n + 1))
permutation = []
while (n> 0):
d = num % n
num = num / n
permutation.append(options.extract(d - 1))
n = n - 1
return permutation
BTW, would you have used the following code in stead of what's in the above extract() method?
self[index] = self.pop()
except IndexError:
pass
November 12th, 2009 at 3:51 pm
You all wrote good solutions which are what I thought they would be. In my next post I will explain some nice mathematical ideas behind these solutions.
rouli: Note that computing n! is not O(n), because multiplications are not O(1) (but are dependent on the number of bits). As can be seen from other solutions though, you don't need that computation.
Goldy & Amir: I think it can be expressed a bit more elegantly.
November 13th, 2009 at 8:59 am
yeah, looking back, I don't have a clue why I opted for the more convoluted way to compute it.
November 13th, 2009 at 10:26 am
We could construct the result at the beginning and swap in-place:
result = range(1, 1 + n)
while n> 0:
p, swap_index = divmod(p, n)
n -= 1
result[n], result[swap_index] = result[swap_index], result[n]
return result
November 14th, 2009 at 3:46 am
I'll post a solution as well, in a few minutes :)
Haven't read the others though
Very nice challenge, it kept me thinking for quite a while!
November 14th, 2009 at 4:04 am
[...] by rmn There are exactly n! different permutations of n numbers. This challenge was about writing a function which is able to enumerate all these permutations, i.e. function [...]
November 16th, 2009 at 6:23 pm
My solution including doctests at: http://pastebin.com/f4c717118
Some of the solutions got a bit complexified, I think I kept it minimalistic, though it's the same algo...
November 24th, 2009 at 11:00 am
The simpliest solution - similar as eric one - based on the "pop" function of Python lists and on the "modulo" operator (no divmod)
values = range(n)
return [values.pop(m%i) for i in range(n, 0, -1)]
November 24th, 2009 at 11:05 am
This solution allows a permutation of any type of list!
n = len(values)
return [values.pop(m%i) for i in range(n, 0, -1)]
for i in range(2*3*4):
print permut(list("abcd"), i)
November 27th, 2009 at 7:51 am
I add a mistake in my code , sorry
here is my last, most-compact shot:
s = range(n)
for j in range(1,n):
m, r = divmod(m,j+1)
s[r], s[j] = s[j], s[ r ]
return tuple(s)
def tester( f, k ):
""" a simple tester function just call tester( permutation_function, k) """
p = [f(k, i) for i in range(fact(k) ) ]
return len(set(p) ) == fact(k)
assert all([ tester(perm, i) for i in range(1,10) ])
sorry for the lazy test before.
and btw here is the "solution"
http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
November 28th, 2009 at 4:13 pm
Well, by definition you need O(n log n) time just to read num, unless you consider machines with registers of length log n.
I'd go with an algorithm similar to Amir's, just replacing "while... n--" with a for loop, but IMHO the more interesting question is how to define a Gray code on permutations, and one of the famous solutions here is the Johnson-Trotter algorithm (http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm ).
January 21st, 2010 at 12:07 pm
There are plenty of algorithms for doing this and even a book written on how to do it called "constructive combinatorics" by Stanton and White.