Как найти слово, гарантированно отсутствующее в наборе?

Question

[Mercury13]

Есть некий алфавит — например, A..Z.
Есть набор слов из этого алфавита.
Придумать слово из этого алфавита, отвечающее двум требованиям.
1. Не очень длинное.
2. Отсутствует в наборе.
Какие есть соображения?

Comments

[Сергей Соколов]

слово любое или словарное (в смысле, из английского языка) ?
Длина слова 1 буква годится? Уточните критерий длины слова: 4 буквы лучше, чем 5 но хуже, чем 3 ?

Answer 1

[Mercury13]

Придумал, причём тупо. Комбинаторикой высчитываем, какой длины (по принципу Дирихле) должно быть наше слово: например, если у нас цифры от 0 до 9 и 125 строк, достаточно взять трёхзначные. Вот мы берём 126 битов (ну или 128 для круглого счёта), из наших чисел берём только трёхзначные и начинаем заполнять биты. Есть, например, 025 — вот в 25-й бит и суём единичку. После этого остаётся найти в битовой маске ноль и преобразовать в нашу строку: на 45-м месте — значит, 045.

Answer 2

[Даша Циклаури]

- хранить набор слов или в hashset или в trie
- выбирая хранения в префиксном дереве, далее генерируешь рандомно длину, далее идешь в глубь по уровням, стараясь или уйти от существующих ключей или останавливаясь на определенном уровне, который образует слово, но которое еще не записано в дереве

a-n-c-h-o-r допустим это одна из ветвей дерева, во главе с буквой "а", ты можешь дойти до буквы "о" и, поняв, что такого слова еще нет "ancho" вернуть его как результат

Comments

[Mercury13]

Префиксное дерево — интересное дело, но найти бы реализацию, да и крупная структура.

[Даша Циклаури]

Mercury13, да ну.... 30 минут на банальном TypeScript

Answer 3

[Wataru]

Еще есть вариант (если у вас все слова разные) - подсчитайте сколько раз каждая длина встречается в наборе.

Если вы видите, что у вас однобуквенных слов меньше, чем букв в алфавите - то можно выдать однобуквенное слово. Иначе, если двух-буквенных слов меньше |alphabet|^2, то можно выдать двубуквенное слово. И так далее. Вот нашли вы минимальную длину.

Чтобы найти и само слово, заведите битмап размером со сколько у вас слов. Потом пройдитесь по словам и если слово нужной длины, поставьте 1 в битмапе с номером равным строке, если ее интерпретировать как число в |alphabet|-ой системе счисления (самый младший символ равен цифре 0). Если число переваливает за размер битмапы, то можно текущую строку проигнорировать. Потом найдите любой 0 бит в битмапе. Его номер переведите назад в |alphabet| систему счисления.

Пример. Алфавит - {a,b}. Слова: "a", "b", "aa", "ab", "bb".

Мы видим 2 однобуквенных слова. Никак. 3 двухбуквенных, но 3 < 2^2 - значит можно выдать двубуквенную строку.

У нас 2 символа в алфавите, интерпретируем a=0, b=1. "aa" = 0, "ab" = 1, "bb" =3. В битмапе останется пустым индекс 2. Это 10 в двоичной системе или "ba" в строках - это и есть ответ. Да еще и лексикографически минимальный.

Если слова могут повторятся, то можно чуть изменить решение: точно также перенумеруйте все возможные слова в вашем алфавите. Сначала будут однобуквенные, потом двубуквенные и т.д. При переводе строки в индекс - также переводите из |alphabet|-ичной системы счисления. Но для слова из l символов прибавляйте смещение |alphabet|^(l-1)+|alphabet|^(l-2)+... |alphabet|^1. Точно так же, если в процессе вычисления видно, что индекс не поместится в битмапу (больше количества строк), то можно забить на эту строку. Поэтому же можно сразу пропускать слишком длинные слова.

Опять же, помечайте бит в битмапе. Потом найдите первый нулевой бит. И назад преобразуйте в строку - сначала найдите смещение (суммируйте степени |alphabet|, пока они не перевалят за текущий индекс). Так вы поймете, сколько символов у вас в строке. Вычтите смещение и переводите индекс в |alphabet|-ичную систему счисления.

Этот вариант в среднем может работать чуть дольше, но все так же очень быстро.

Еще, оба эти варианта самые экономные по памяти.

Comments

[Mercury13]

Ну да, повторили моё решение.

[Wataru]

Mercury13, Я свое решение писал весьма долго. Когда начал писать - вашего не видел.

Answer 4

[hint000]

https://ru.wikipedia.org/wiki/Фильтр_Блума

— это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая проверять принадлежность элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.