@Mercury13
Программист на «си с крестами» и не только

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

Есть некий алфавит — например, A..Z.
Есть набор слов из этого алфавита.
Придумать слово из этого алфавита, отвечающее двум требованиям.
1. Не очень длинное.
2. Отсутствует в наборе.
Какие есть соображения?
  • Вопрос задан
  • 124 просмотра
Решения вопроса 3
@Mercury13 Автор вопроса
Программист на «си с крестами» и не только
Придумал, причём тупо. Комбинаторикой высчитываем, какой длины (по принципу Дирихле) должно быть наше слово: например, если у нас цифры от 0 до 9 и 125 строк, достаточно взять трёхзначные. Вот мы берём 126 битов (ну или 128 для круглого счёта), из наших чисел берём только трёхзначные и начинаем заполнять биты. Есть, например, 025 — вот в 25-й бит и суём единичку. После этого остаётся найти в битовой маске ноль и преобразовать в нашу строку: на 45-м месте — значит, 045.
Ответ написан
dasha_programmist
@dasha_programmist
ex Software Engineer at Reddit TS/React/GraphQL/Go
- хранить набор слов или в hashset или в trie
- выбирая хранения в префиксном дереве, далее генерируешь рандомно длину, далее идешь в глубь по уровням, стараясь или уйти от существующих ключей или останавливаясь на определенном уровне, который образует слово, но которое еще не записано в дереве

a-n-c-h-o-r допустим это одна из ветвей дерева, во главе с буквой "а", ты можешь дойти до буквы "о" и, поняв, что такого слова еще нет "ancho" вернуть его как результат
Ответ написан
wataru
@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|-ичную систему счисления.

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

Еще, оба эти варианта самые экономные по памяти.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
hint000
@hint000
у админа три руки
https://ru.wikipedia.org/wiki/Фильтр_Блума
— это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая проверять принадлежность элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы