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

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

Edited for formatting -timlWell 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]