Нахождение n-бит. кода замены с минимальной разницей соседей

[SereNEES]

Помогите решить такую задачу:
Построить код замены, удовлетворяющий следующим условиям:
1) состоит из всех $2^n$ n-битных чисел
2) не одно число не повторяется
3) при изменении любого из n бит значение числа не превосходит K

Существует ли такой код, если $K < \frac n 2$ ?

Написал программу расчета генными алгоритмами - для 8-битного кода K=128, меньше не находит.
Пробовал идти "напролом" - полным перебором, получается $О((2^n))!$. При n=4 полный обсчет на компьютере занимает по моим подсчетам год.

[venco]

SereNEES в сообщении #333841 писал(а):

1) состоит из всех n! n-битных чисел

Перечислите $4!=24$ различных 4-х битных числа.

-- Вт июн 22, 2010 10:38:39 --

SereNEES в сообщении #333841 писал(а):

3) при изменении любого из n бит значение числа не превосходит K

Может быть, изменение значения не превосходит K?
Или я условия не понял, или идентичная перестановка подходит - у неё изменение старшего бита даёт изменение значения как раз $2^{n-1}$.
Можете привести пример кода с примером изменений?

[SereNEES]

Прошу прощения, ошибся - необходимы все $2^n$ элементов

Пример:

для 3-битного кода:

Код перестановки (код грея)
Индекс Значение
000 000
001 001
010 011
011 010
100 110
101 111
110 101
111 100

Код Грея удовлетворяет только частично третьему условию. Необходимо полное соответствие.

К примеру, для n-битного кода:
можно составить таблицу $2^n$ строк на n столбцов, заполнив таким способом:
в ячейку I х J помещаем индекс соседа по J-тому биту I-го элемента
Пример для n=3:

001 010 100
000 011 101
011 000 110
101 110 000
100 111 001
111 100 010
110 101 011

Этим мы задаём граф связей - каждый элемент связан с n другими элементами. Вершин графа $2^n$.

Затем циклом по всем I и J проходим и ищем разницу элемента и его соседа. Максимальная разница и сравнивается с K

[venco]

SereNEES в сообщении #333873 писал(а):

Код Грея удовлетворяет только частично третьему условию. Необходимо полное соответствие.

Всё равно непонятно. Приведите пример несоответсвия для кода Грея, и для идентичного кода (индекс = значение).

[ИСН]

Нет, как раз понятно. Товарищ хочет, чтобы не только соседние коды различались одним битом, но и чтобы все коды, различающиеся одним битом (неважно каким!), были...

[venco]

ИСН в сообщении #333905 писал(а):

Нет, как раз понятно. Товарищ хочет, чтобы не только соседние коды различались одним битом

Вот это Вы откуда взяли?

[ИСН]

Из определения кодов Грея, а что?

[SereNEES]

Да, ИСН, вы правы - "соседей" по всем битам

[SereNEES]

Ну же, кто-нибудь, хотя бы посоветуйте алгоритм побыстрее просчитать всё это дело.