Имеем 256 коробок, в которых находятся карточки с числами из набора 0..255 (расбросаные по одной в каждую коробку, случайно).
Необходимо сохранить состояние (в какой коробке какая карточка) в меньшем нежели 256 байт объеме информации.

легко в 255 байт!!!
256-ой получается из 255-ти

Хочется ещё меньше, по тому же принципу. т.е. к примеру в первой коробке может быть один из 256 вариантов , во второй коробке уже 255, в следующей 254 и т.д. Соответственно под каждую коробку выделять по байту - излишне.

semibug, 
Сжимать можно только те последовательности у которых есть за закономерности. А тут последовательность случайна.

Добавлено через 3 минуты и 50 секунд
А сори не подумал. Есть тут закономерность. Можно построить дерево и закодировать дерево путем обхода дерева. Выбо левой или правой вершины определяет единичка или нолик соответственно получится 256 бит.

Lipetsk, ответ рулит!

Думаю можно сжать еще больше.

Самый простой вариант - любой алгоритм сжатия информации. Наверняка хоть чуть, а сожмет.

Или вот такой странный вариант (на лету придумываю - могу и наврать):

1. Представляем коробки как 256-элементный массив типа байт.
2. Далее начинаем паковать информацию в память. В первые 128 байт памяти загоняем номера коробок, содержащих карточки с номерами от 0 до 127. В каждый байт памяти по номеру коробки. Т.е. потратили Байт*128=1024бита памяти.
3. Убираем из массива коробки, номера которых уже сохранены в памяти. Остается массив из 128 коробок.
4. Т.к. максимальный номер элемента в оставшемся массиве коробок =127, для хранения номеров (после перенумерации) достаточно 7-бит на номер.
5. Записываем еще 64 номера в 7-битном формате, убираем учтенные коробки из массива. Потратили еще 7бит*64=448 бит.
6. Теперь в массиве осталось 64 коробки. 6-бит достаточно.
7. Регистрируем еще 32 коробки в 6-битном формате. Тратим еше 192 бита.
8. Убираем зарегистрированные. Регистриуем 16 коробок в 5-битном формате. Еще 80 бит.
9. Убираем зарегистрированные. Регистриуем 8 коробок в 4-битном формате. Еще 32 бита.
10. Убираем зарегистрированные. Регистриуем 4 коробоки в 3-битном формате. Еще 12 бит.
11. Регистриуем 2 коробоки в 2-битном формате. Еще 4 бита.
12. Регистриуем 1 коробоку в 1-битном формате. Еще 1 бит.
13. Оставшаяся коробка находится там, гду ей указано Lipetsk-ом.
14. Итого потратили 1024+448+192+80+32+12+4+1=1793, коее число бит лекго помещается в 225 байт, да еще и огромный хвост от последнего байта останется.

_Y_, cool, выглядит жизнеспособно.
Развивая мысль, пытаюсь определить теоретический предел - для 256 коробок в результате перестановок получаем 256! вариантов (8,578177753×10⁵⁰⁶), если я правильно помню математику.
Такое число укладывается в 211 байт.
Но с какого боку подойти, чтобы преобразовать исходные данные в эти 211 байт идей нет (

да просто посчитать номер перестановки и его закодировать в битах

номер можно посчитать, как число в специфической системе счисления - у которой основание меняется от разряда к разряду

i[0]+255*i[1]+255*254*i[2]+...
i[k] - номер карточки в коробке k, но с учётом пропусков уже использованых карточек

например, если i[0]=5, то i[1] будет соответствовать номеру карточки, если он меньше 5, и отличаться на 1, если он больше 5

Достаточно пронумеровать в лексикографисеском порядке все разложения и вернуть номер разложения.