A quick algorithms problem

Here’s a quick little problem to try. My solution (in python) is below but I’d love to see different ways to solve it.

Problem

Assume you have a list of 8 items numbered 0 through 7, however they are in some random order.  You would like to encode the order they are in using the least number of bits possible.

There are 8! possible options for how they are ordered, which could conceivably be numbered 1..40320.  This could then be encoded as a 16-bit int.

Find an efficient way to determine the correct encoding for a given list, and vice-verse to determine the ordering for a given encoding.

Solution

def decode(x):
    digits = [0,1,2,3,4,5,6,7]
    values = []
    for modval in [5040, 720, 120, 24, 6, 2, 1]:
        index, x = divmod(x, modval)
        digit = digits[index]
        digits.remove(digit)
        values.append(digit)
    values.append(digits[0])
    return values

def encode(values):
    result = 0
    digits = [0,1,2,3,4,5,6,7]
    for mulval, value in zip([5040, 720, 120, 24, 6, 2, 1], values[:-1]):
        index = digits.index(value)
        result += mulval*index
        digits.remove(value)
    return result

for x in range(8*7*6*5*4*3*2*1):
    values = decode(x)
    xx = encode(values)
    assert x == xx

2 thoughts on “A quick algorithms problem

  1. Here’s a solution you might like. It does a weird kind of bubble sort. It has the following advantages:
    – Can reorder arbitrary lists
    – Optimum ordering compression
    – Only has swaps, no removing elements from arrays

    def encode(values):
        val = 0
        for i in range(1, len(values)):
            j = i
            while(values[j] < values[j-1] and j > 0):
                values[j], values[j-1] = values[j-1], values[j]
                j -= 1
            val *= i + 1
            val += i - j
        return val
    
    def decode(val, sortedvalues):
        values = sortedvalues
        for i in reversed(range(1, len(values))):
            val, j = divmod(val, i+1)
            j = i - j
            while(j < i):
                values[j+1], values[j] = values[j], values[j+1]
                j += 1
        return values
    
    values = [0,992,12,13131,48484,222,2999,1,42,391]
    print(values)
    encoded = encode(values)
    decoded = decode(encoded, sorted(values))
    print(decoded)
    

    Edited for formatting -timl

  2. Well I know it’s pretty late but here’s mine… Similar to timl’s except does not hardcode the modulo values.

    [code language="python"]
    def encode(l, units=1):
    if len(l)<=1:
    return 0
    x = l.index(len(l)-1)
    new_list = l[:x] + l[x+1:]
    return units*x + encode(new_list, units*len(l))

    def decode(a, n):
    l = [0]
    units = factorial(n)
    for m in range(1, n):
    units = units / (m+1)
    x, a = divmod(a, units)
    l.insert(x, m)
    return l

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

    import random
    N = 8
    l = range(N)
    random.shuffle(l)
    x = encode(l)
    y = decode(x, N)
    print l
    print x
    assert y==l
    [/code]

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>