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!

This entry was posted in Challenges, computer science, Programming and tagged , . Bookmark the permalink.

15 Responses to Small Programming Challenge no. 5 – Generating a Permutation

  1. goldy says:

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

  2. rouli says:

    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]

  3. eric says:

    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 …

  4. Amir says:

    [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]

  5. lorg says:

    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.

  6. rouli says:

    yeah, looking back, I don’t have a clue why I opted for the more convoluted way to compute it.

  7. Amir says:

    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]

  8. rmn says:

    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!

  9. Pingback: Enumerating permutations « cplusplus.co.il

  10. yuval says:

    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…

  11. Jy-ce says:

    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]

  12. Jy-ce says:

    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]

  13. eric says:

    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

  14. Rani says:

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

  15. Naccache says:

    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.