miksoftА стоит ли задача найти множество максимально возможного размера? Или пойдет любое?

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

miksoftХотя, может, вам не стоит заморачитваться на это "расстояние" и просто часть (в приведенном примере 3-1=2) символов выделять под контрольную сумму?

Объясните подробнее что имеете в виду. Не важно каим способом решается задача. злавное результат. - устойчивость строки к ошибкам ввода (оператор должен вручную вводить коды при этом необходимо гарантировать, что если он ошибется n раз, то не введет случайно другой существующий код)

miksoftВозможно, в поисках вам поможет то, что "отличается от всех других сгенерированных до этого строк на n символов" - это называется "расстояние".
Подробнее - см. статью Анализ строк , параграф 3.2 Спасибо за ссылку. Посмотрю.

miksoft Автор Алексей miksoftА стоит ли задача найти множество максимально возможного размера? Или пойдет любое?

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

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

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

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

Есть идеи?

miksoft Автор Алексей miksoftА стоит ли задача найти множество максимально возможного размера? Или пойдет любое?

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

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

Ошибочка ввода :)

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

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

Есть идеи?

miksoft Автор Алексей miksoftХотя, может, вам не стоит заморачитваться на это "расстояние" и просто часть (в приведенном примере 3-1=2) символов выделять под контрольную сумму?
Объясните подробнее что имеете в виду. Не важно каим способом решается задача. злавное результат. - устойчивость строки к ошибкам ввода (оператор должен вручную вводить коды при этом необходимо гарантировать, что если он ошибется n раз, то не введет случайно другой существующий код) Код Хемминга

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

Пример 1. Пусть имеем основной код 100110, то есть К = 6. Следовательно, L = 3 и дополнительный код равен

010 # 011 # 110 = 111,

где # — символ операции поразрядного сложения, и после инвертирования имеем 000. Теперь вместе с основным кодом будет передан и дополнительный. На приемном конце вновь рассчитывается дополнительный код и сравнивается с переданным. Фиксируется код сравнения (поразрядная операция отрицания равнозначности), и если он отличен от нуля, то его значение есть номер ошибочно принятого разряда основного кода. Так, если принят код 100010, то рассчитанный в приемнике дополнительный код равен инверсии от 010 # 110 = 100, то есть 011, что означает ошибку в 3-м разряде.

Но насколько я понял этот метод не подходит для этой задачи. Это так (читайте предыдущее сообщение)

mayton АлексеiУточнение: это необходимо для того, чтобы при вводе кодов вручную и опечатке, не получалось так, что пользователь ввел другой существующий код.

Коды и идентификаторы нельзя вводить с опечатками.

В случае с ФИО, если оператор набирает:


можно, задавшись критерием близости (расстояние Хэмминга, созвучие слогов или букв, определить что нужно было ввести:


В случае с кодами, промах в одну цифру может дать парадоксальный результат. Скорее всего будет выбран не тот ID, хотя алгоритм отработает верно. А вводить эвристические коэффициенты в промышленную систему это значит поставить её в состояние "вечной отладки".

Может быть вам стоит подумать над тем, чтобы оператор не вводил код вручную а выбирал его из умного ComboBox c дополнительным полем типа Комментарий ?

1. Код может быть введен с опечатками
2. Система не ставит перед собой целью исправления кода

zloy denТакже было бы неплохо почитать книху Блэйхута "теория и практика кодов, контроллирующих ошибки". но это если времени много

Можно... но так описано как генерировать строки, которые гарантированно отличаются на N символов до предыдуще сгенерированных строк?

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

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

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

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

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

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.Если не секрет - как вы ее прикрутили к русским буквам?Мне нужно было использовать символы английского алфавита. А почему должна быть проблема использования русских символов? Можно для каждого символа есть всей бинарный код. достаточно договориться о кодировке.Еще недавно вам не нравилось, что "код Хемминга предусматривает работу с двоичными кодами".

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