Here's an interesting problem: "Encode the order of a 52-card deck in 32 bytes". It's not as easy as it sounds! My solution is below.
#include <stdio.h> #include <stdlib.h> /* Encode array of ordinals [0 .. n-1] by using an ordered set as * a binary search tree, removing the each leaf traversed until the * set has 1 member. Traversal paths are the encoding. */ int encodeOrder(int* input, int* output, int n) { int i,j; int* o = malloc(sizeof(int)*n); /* ordered set */ for (i = 0; i < n; i++) { o[i] = i; } int s = n; /* ordered set size */ int k = 0; /* output index */ for (i = 0; i < n; i++) { int a = 0; /* interval [a,b] */ int b = s-1; int c; /* center of [a,b] */ while (b - a > 0) { /* binary search in o */ int x; c = (b - a) / 2 + a; if (o[c] >= input[i]) { output[k++] = 0; /* set next "bit" to 0 */ b = c; } else { output[k++] = 1; /* set next "bit" to 1 */ c ++; a = c; } } for (j = b+1; j < s; j++) { /* remove ordinal from o */ o[j-1] = o[j]; } s --; } free(o); return k; } /* Traverse ordered set as in encoding, returning and removing each * leaf as the original ordinals. */ int decodeOrder(int* input, int* output, int n) { int i,j,l; int* o = malloc(sizeof(int)*n); /* ordered set */ for (i = 0; i < n; i++) { o[i] = i; } int s = n; /* ordered set size */ int k = 0; /* input index */ for (i = 0, k = 0; i < n-1; i++) { int a = 0; /* interval [a,b] */ int b = s-1; int c; /* center */ while (b - a > 0) { /* binary search in o */ int x; c = (b - a) / 2 + a; if (input[k] == 0) /* if bit is 0, go left */ { b = c; } else { c ++; a = c; } k ++; } output[i] = o[c]; /* set next ordinal */ for (j = c+1; j < s; j++) { /* remove ordinal from o */ o[j-1] = o[j]; } s --; } output[n-1] = o[0]; /* last ordinal is trivial */ free(o); return k; }