Есть таблица из 45*45 = 2025 комбинаций размещений с повторениями. Нужно передавать информацию, соответствующую определенной комбинации. Для этого нужно 11 бит (передается индекс массива). Восстановить комбинацию на приемной стороне запросто - по принятому индексу таблицы. А как лучше разместить комбинации в таблице, чтобы процесс кодирования происходил тоже "влет"? Не перебором по таблице же? Можно, конечно, судить область поиска, согласно "весу" (например, для (3,5) "вес" равен 8), и искать индекс среди пар с таким же "весом", но это тоже не оптимально. Может, есть какие-то известные решения?

Если добавить 1 бит, можно будет левыми 6 бит кодировать строку, а правыми - столбец.

Если Вы будете хранить элементы массива на передающей стороне в сортированном виде, то для поиска необходимо будет только log2(N) операций, для Вашего случая - 11. Это оптимальный способ. Ключевое слово для гугля - "бинарный поиск".

Спасибо. Но как раз вопрос возник из-за накладываемого ограничения на число передаваемых бит.



Спасибо. Ясно, значит, всё-таки без поиска не обойтись. Я надеялся, что существует какой-то хитрый метод, использующий манипуляции с битами, позволяющий эффективно закодировать.

UPD:
Расписал на бумажке комбинации. Понял, что можно обойтись без поиска и вообще без таблицы на передающей стороне. Для пары (i,j) индекс будет вычисляться как 45*(i-1)+j. Его и передавать. А на приемной стороне уже из таблицы прямо по индексу брать эту пару.

+1. Это как бы само собой очевидно, смысл экономить один бит...