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