какой алгоритм или куда копать?

@pretzel · Регистрация: 25.09.2017

Студворк — интернет-сервис помощи студентам

есть набор слов W, состоящих из букв алфавита a..z. буквы одни и те же, наборы разные:

слово может быть длиной 2 и больше букв
в слове любая буква алфавита может встречаться только 1 раз (или 0 раз — это слово без этой буквы). соотвественно, слово не может быть длиньше |алфавит|

что известно о наборе:

сколько раз встречается каждая буква алфавита в наборе. другими словами, в скольких словах из набора, помните, у нас нет слов с 2мя+ одинаковыми буквами
сколько раз буква X встречается в одном слове с буквой Y. симметричная матрица (полматрицы или граф) с нулевой главной диагональю количеств, где клетка [X,Y]=число, где X,Y принадлежат алфавиту

надо определить:

все слова в наборе, порядок букв неважен
количество слов с 2,3,..n буквами
количество всех слов в наборе

любое из.

@anonimus · 25.09.2017, 17:22

Регулярные выражения используй

@pretzel · 25.09.2017, 18:04 **[ТС]**

Сообщение от anonimus

Регулярные выражения используй

как регулярка учитывает числа в матрице?
что если в алфавите будет 10000 элементов? (необязательно a..z)
здесь чтото жадное, графовое или .. чемто похожее на японские кроссворды (но не оно)
просто не могу даже тему нагуглить

@Massaraksh7 · 25.09.2017, 19:41

Боюсь, только перебором.

@Shamil1 · 25.09.2017, 21:19

Можно пример входных данных с правильным ответом?

@pretzel · 25.09.2017, 22:50 **[ТС]**

пример:
1) A в словах встречается 8 раз; B - 6; C - 8; D - 6; E - 6; F - 2
2) попарная встречаемость букв в словах в след.таблице

C#
1
2
3
4
5
6
7
 A B C D E F
 0 2 6 4 4 0 A
   0 2 4 4 2 B
     0 4 4 0 C
       0 6 0 D
         0 0 E
           0 F

ответ:
BF: 2 раза
AC: 4 раза
BCDE: 2 раза
ACDE: 2 раза
ABDE: 2 раза
либо такой ответ: в наборе 12 слов

Добавлено через 24 минуты
хмм, вроде, метод резиновой уточки действительно работает
из 1) видим, что A и C встречаются по 8 раз, но между собой они встречаются всего в 6ти словах. значит есть еще 2 слова с A и без C и 2 слова с C и без A, т.е. как минимум уже 10 слов.. дальше.. другие буквы-цифры должны увеличить или подтвердить этот результат.. это про вариант - сколько слов вообще, в принципе он мне тоже подходит.. завтра на свежую голову обдумаю подводные камни

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@pretzel 0 / 0 / 0 Регистрация: 25.09.2017 Сообщений: 3

	какой алгоритм или куда копать? 25.09.2017, 14:59. Показов 723. Ответов 5 Метки нет (Все метки) есть набор слов W, состоящих из букв алфавита a..z. буквы одни и те же, наборы разные: слово может быть длиной 2 и больше букв в слове любая буква алфавита может встречаться только 1 раз (или 0 раз — это слово без этой буквы). соотвественно, слово не может быть длиньше \|алфавит\| что известно о наборе: сколько раз встречается каждая буква алфавита в наборе. другими словами, в скольких словах из набора, помните, у нас нет слов с 2мя+ одинаковыми буквами сколько раз буква X встречается в одном слове с буквой Y. симметричная матрица (полматрицы или граф) с нулевой главной диагональю количеств, где клетка [X,Y]=число, где X,Y принадлежат алфавиту надо определить: все слова в наборе, порядок букв неважен количество слов с 2,3,..n буквами количество всех слов в наборе любое из. 0

@anonimus 2184 / 1255 / 143 Регистрация: 28.04.2010 Сообщений: 4,592
	25.09.2017, 17:22
	Регулярные выражения используй 0

@Massaraksh7 Айлурофил 514 / 447 / 112 Регистрация: 27.05.2017 Сообщений: 2,688 Записей в блоге: 5
	25.09.2017, 19:41
	Боюсь, только перебором. 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,885
	25.09.2017, 21:19
	Можно пример входных данных с правильным ответом? 0