Годится ли Брезенхем для Хемминга?

[spamsink]

Стоит задача эффективно и без использования рандомизации строить N M-битных кодов, как можно более удаленных друг от друга в смысле Хемминга, в которых ровно K бит равны 1 (в типичном случае N в разы, а то и на порядки меньше, чем C(M, K)). Например, нужно получить пару тысяч 32-битных кодов с 3 битами, равными 1 (C(32, 3) = 4960); или пару десятков тысяч 32-битных кодов с 16 битами, равными 1 (C(32, 16) = 601080390, что всё ещё не ужас-ужас-ужас).
Я предлагаю пройтись (например, хаком Госпера для небольших M) по всем C(M, K) от "K младших единиц" до "K старших единиц", более или менее равномерно выбирая в общей сложности N кодов с помощью Брезенхема.
Что скажете?

Comments

[vgramagin.livejournal.com]

Лично я - не возражаю!

[vak]

Звучит как "ватман для кульмана". :)

[spamsink]

Дык! Я еще подумывал, не озаглавить ли пост "Брезенхемминг".

[vak]

Вот этот метод не проще будет?
http://gaussianwaves.blogspot.com/2008/05/construction-of-hamming-codes-using.html

[spamsink]

Там метод построения кодов Хемминга, исправляющих одну ошибку. У меня задача другая.

[vak]

А, ну да...

[scolar.livejournal.com]

А откуда берётся это неестественное требование обойтись без рандомизации? При таких соотношениях мощностей множеств энтропии-то совсем чуть-чуть нужно.

[spamsink]

Алгоритм, не использующий рандомизации, более убедителен. В принципе, можно и без рандомизации вместо Брезенхема взять какое-нибудь число, близкое к N и взаимно простое с C(M, K), и знай себе ходить по кругу N раз - может даже быстрее получиться, если написать функцию для получения комбинации (K из M) по ее порядковому номеру, что должно быть несложно.

[spamsink]

Вопрос, собственно, можно переформулировать так: какая-нибудь псевдослучайная выборка - лучшее, что можно придумать, или есть способ строить такие множества, гарантирующий максимизацию среднего расстояния?