wiksхм, интересная задачка, стало интересно, начал искать в инете, случайно наткнулся на преобразование адамаpа-уолша. нашел пример, окзывается, там строится очень интересная матрица http://www.enlight.ru/demo/faq/smth.phtml?query=alg_comp_aw , вот цитата:


Расширил в экселе еще на один порядок, получилось:


Можно заметить закономерность: для матрицы N x N мы имеем N строк из N двоичных чисел (если заменить "-1" на ноль).
При этом ЛЮБЫЕ две строки (в том числе соседние) отличаются друг от друга в (N-1) позициях.

Если бы у меня была подобная исходной задача, примерно такая:
создать алгоритм генерации 2^K двоичных чисел, отличающихся не менее чем в N позициях

то решить ее можно например так:
1. создать вот такую матрицу (с нулем вместо "-1") размерности R x R, где R = N + K + 1
2. я имею R строк, отличающихся в N + K позициях, а мне нужно 2^K строк в N позициях. Что делать?

Допустим
Для каждых двух соседних строк (то есть R-1 раз):
1)находим К «позиций размножения» - это К позиций, отличающихся в этих строках
2)Перебираем 2^К вариантов, генерируя из нижней соседней строки 2^K строк
3. В итоге имеем (R-1) * (2^K) +1 строк (+1 это самая первая строка, она не «размножается»)

хм, ну ладно, тогда так:
Для каждых двух соседних строк:
1)находим X «позиций размножения», где X = log2( (2^K) / (R-1)) = K / log2(R-1)
2)Перебираем 2^X вариантов
3. В итоге имеем (R-1) * ( 2 ^ X) +1 = 2^K+1 строк, отличающихся не менее чем в N позициях.

Остался вопрос, как выбирать эти Х позиций, чтобы уменьшить кол-во одинаковых «последовательностей» между смежными строками? Можно выбирать отличающиеся позиции «через одну»?

И еще, если к матрице подставить снизу инвертированную, то можно пользоваться и такой «удвоенной».

Пойдет?

Спасибо большое за предлагаемое решение. Постараюсь понять предлагаемый алгоритм ))

White OwlЧего-то я не понял, а какой смысл в этой задаче?
Если все это " необходимо для того, чтобы при вводе кодов вручную и опечатке, не получалось так, что пользователь ввел другой существующий код. " То увы, вас никакая уникальность кодов не спасет - оператор всегда может ошибиться строкой и набить не тот код просто потому что забыл линейку передвинуть.


White Owl
Задача забавна, но бессмысленна.
В реальном мире это решается выпадающими списками и сканерами штрихкодов.


2. Пользователь указывает свой персональный код в бумажной анкете (это исключает использование штрих кода). После этого оператор должен вручную ввести пользовательский код в систему (нет ни каких выпадающих списков). Таковы условия ТЗ.
1. Да, оператор может ошибиться и ввести код, который принадлежит другому пользователю. Этот тип ошибок ввода отслеживается другими методами и в данном вопросе не имеет значения. (решается путем добавления в код уникальной информации, относящейся только к пользователю)

Задача: уменьшить вероятность того, что оператор нажал один или несколько раз не ту клавишу.

Опережая вопрос по поводу того, что успользуется уникальная информация о пользователе - значит нет проблемы: нет это не так.

например используется логин как часть кода
логин1: grot
логин2: grod

логин должен быть уникальным но может отличаться всего на 1 символ. Это означает, что оставшаяся часть кода должна быть устойчива к ошибкам ввода.

Вот так. Есть предложения?

wiksПравильно вот так:

1. создать вот такую матрицу (с нулем вместо "-1") размерности R x R, где R = 2*(N + K)
2. я имею R строк, отличающихся в N + K позициях, а мне нужно 2^K строк в N позициях

Для каждых двух соседних строк (R-1 раз):
1)находим X «позиций размножения», где X = log2( (2^K) / (R-1)) = K / log2(R-1)
2)Перебираем 2^X вариантов, генерируя последовательно (из нижней из этих двух строк) на выход алгоритма 2^X строк
3. В итоге имеем на выходе алгоритма (R-1) * ( 2 ^ X) = 2^K строк, отличающихся не менее чем в N позициях.

Спасибо за алгоритм! Постараюсь написать програмку и выложу ее здесь для обсуждения!

wiksне, не пойдет алгоритм :-(((

вот это не пойдет:
Перебираем 2^X вариантов, генерируя последовательно (из нижней из этих двух строк) на выход алгоритма 2^X строк

исходные строки в матрице действительно отличаются в N/2 позициях, а вот генерируемые - между собой уже не отличаются на требуемое кол-во позиций.

Бывает, ступил, плохой вариант....

Ничего! Добьемся решения!

У кого какое мнения?

Damienя бы просто сгенерил огромную таблицу (32^5), перебирающую все возможные значения т.е. от ААААА до ЯЯЯЯЯ и перемещался по ней с определенным шагом (32^3), выбирая заведомо отличающиеся друг от друга значения. Либо сразу создавать таблицу так, чтобы генератор выдавал очередную строку с тем же шагом.
Процедуры перебора значений, при заданном наборе символов, уже написаны для практически всех языков.
Уникальность кодов будет гарантироваться занесением в таблицу значения False напротив вбитого ранее кода.
В этом решении, конечно, выгоднее использовать БД, хотя она уже наверняка предусмотрена в такой программе?

P.S.
выше заданные значения нуждаются в проверке. За длину алфавита взято 32, хотя лучше выкинуть всякие там Ъ Ь Й...

Вариент не подходит, т.к. необходимо сгенерировать все коды сразу и хранить их в БД (даже те, которые еще не используются).

RMih2. Пользователь указывает свой персональный код в бумажной анкете (это исключает использование штрих кода). После этого оператор должен вручную ввести пользовательский код в систему (нет ни каких выпадающих списков). Таковы условия ТЗ.
1. Да, оператор может ошибиться и ввести код, который принадлежит другому пользователю. Этот тип ошибок ввода отслеживается другими методами и в данном вопросе не имеет значения. (решается путем добавления в код уникальной информации, относящейся только к пользователю)

Задача: уменьшить вероятность того, что оператор нажал один или несколько раз не ту клавишу.

Опережая вопрос по поводу того, что успользуется уникальная информация о пользователе - значит нет проблемы: нет это не так.

например используется логин как часть кода
логин1: grot
логин2: grod

логин должен быть уникальным но может отличаться всего на 1 символ. Это означает, что оставшаяся часть кода должна быть устойчива к ошибкам ввода.

Вот так. Есть предложения?
Что же все-таки мешает хранить в персональном коде пользователя контрольные цифры/буквы?
По-моему, это существенно уменьшит вероятность ошибок ввода. Такой подход, например, используется в номерах банковских счетов и в штрих-кодах.[/quot]

Допустимый вариант. Буду изучать как это сделать (добавить и передать контрольную сумму). Спасибо.

Николай1 Автор Алексей miksoft Автор Алексей
Ошибочка ввода :)

1. Данный алгоритм не подходит, т.к. предусматривает предварительный отбор всех строк и дальнейшее их использование.

2. Это как раз связано с 1. Генерация должна выполняться на основании предыдущей строки. Например: для чисел на основании 1 генерируется 2 - 3 - 4 - 5 и т.д. но здесь не предусмотрена "устойчивость" к ошибкам ввода. Необходимо реализовать такой алгоритм, который на основании AAA сгенерирует ABB, BAB, BBA, ACC, CAC, CCA (это в случае с учтойчивостью для одной ошибки ввода). Т.е. если пользователь введет ABC - то будет известно, что эта строка ошибочная (как это не сейчас не важно - все сгенерированные строки, отвечающие критериям устойчивости будут храниться в БД)

Есть идеи?Не обязательно все результирующее множество генерить сразу, можно генерить новые строки по мере необходимости.
Правда, для этого придется хранить все ранее выданные. И с каждой новой строкой будет медленнее...

И как? :) Можете привести алгоритм? и его вычислительную сложность? Если этот алгоритм предусматривае предварительную выборку всех строк, сгенерированных до этого ид БД (например), то не подходит... таких строк будут миллионы.

Операторы вобьют миллионы записей за короткое время?
Да и, вообще, какая-то странная задача.
Сначала в одной системе надо сгенерировать коды, потом перенести их на бумагу, с которой оператор снова их введет.
Как-то странно это выглядит, не находите?

Нет не нахожу. Выглядит совершенно нормально, т.к. отсутствует возможность подключения одной системы к другой.

Задача решена использованием контрольной суммы CRC32. Всем большое спасибо!!!!!!!!!!!

miksoft Автор АлексейЗадача решена использованием контрольной суммы CRC32.Если не секрет - как вы ее прикрутили к русским буквам?

Мне нужно было использовать символы английского алфавита. А почему должна быть проблема использования русских символов? Можно для каждого символа есть всей бинарный код. достаточно договориться о кодировке.

miksoft Автор Алексей miksoft Автор АлексейЗадача решена использованием контрольной суммы CRC32.Если не секрет - как вы ее прикрутили к русским буквам?Мне нужно было использовать символы английского алфавита. А почему должна быть проблема использования русских символов? Можно для каждого символа есть всей бинарный код. достаточно договориться о кодировке.Еще недавно вам не нравилось, что "код Хемминга предусматривает работу с двоичными кодами".

Присто не понимал коды Хеменга.