Categories
Challenges computer science Programming

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!

15 replies on “Small Programming Challenge no. 5 – Generating a Permutation”

[python]
def permute(n,num):
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
[/python]

use some better data structure (hashed linklist) for options to get the remove(val) in O(1)

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:
[Python]
def permutate(n,num):
“”” 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
[/Python]

I love challenges !!

here is my shot

[python]
def perm(n, m):
index , perm =range(n) , [None]*n
for i in range(n):
p = m%(n-i)
perm[ index[p] ]=i
del index[p]
return perm

[/python]

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 …

[CODE]
class Options(list):
“””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
[/CODE]

BTW, would you have used the following code in stead of what’s in the above extract() method?
[CODE]
try:
self[index] = self.pop()
except IndexError:
pass
[/CODE]

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.

We could construct the result at the beginning and swap in-place:
[CODE]
def permute(n, p):
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
[/CODE]

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!

The simpliest solution – similar as eric one – based on the “pop” function of Python lists and on the “modulo” operator (no divmod)

[Python]
def permut(n, m):
values = range(n)
return [values.pop(m%i) for i in range(n, 0, -1)]
[/Python]

This solution allows a permutation of any type of list!

[Python]
def permut(values, m):
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)
[/Python]

I add a mistake in my code , sorry

here is my last, most-compact shot:
[python]
def perm(n, m):
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) ])

[/python]

sorry for the lazy test before.

and btw here is the “solution”
http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

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

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.

Leave a Reply to lorg Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.