Форум программистов, компьютерный форум CyberForum.ru

Комбинаторика. Вывести все слова, которые можно составить из данных букв - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
11.07.2015, 18:54     Комбинаторика. Вывести все слова, которые можно составить из данных букв #1
Всем привет.

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

Задание:
Вывести все слова, которые можно составить из данных букв, длинна слова соответственно тоже дана.

Вот я и подумал. Полюбому надо использовать размещение из n(количество всех данных букв) по m(длина слова). Начал рыть просторы, но ничего толком не нашел. Были варианта, но все они работают очень долго, так как на вход подаются довольно большие значения n и m(например n = 20, m = 13).

Немогли бы вы, могучии знатоки алгоритмов размещения, помочь мне в с данным вопросом, тоесть предоставить алгоритм, который не работал бы пол часа, ну или дать ссылки, где бы я мог почитать полезную информацию?

Спасибо за внимание.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2015, 18:54     Комбинаторика. Вывести все слова, которые можно составить из данных букв
Посмотрите здесь:

можно ли из букв слова Х составить слово У C++
Вывести те слова, которые отличаются от последнего слова и удовлетворяют условию, что в слове нет повторяющихся букв C++
Вывести только те слова сообщения, которые содержат не более чем n букв C++
C++ Вывести только те слова сообщения, которые содержат не более чем n букв
C++ Определить, можно ли из букв одного слова составить другое
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11843 / 6822 / 771
Регистрация: 27.09.2012
Сообщений: 16,915
Записей в блоге: 2
Завершенные тесты: 1
11.07.2015, 19:01     Комбинаторика. Вывести все слова, которые можно составить из данных букв #2
Цитата Сообщение от Leonman Посмотреть сообщение
но все они работают очень долго
угу
Цитата Сообщение от Leonman Посмотреть сообщение
(например n = 20, m = 13)
если все буквы разные, то у нас имеется 81920000000000000 (2013) различных комбинаций.

По сути, у нас просто анаграмма.
Как вариант - достать словарик слов и в нем искать слова, которые можно составить из данных букв :-)
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
11.07.2015, 19:43  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #3
Croessmah, собственно это второй этап. У меня была такая идея, что сначала я получу массив всевозможных слов, которые составленны из данных мне букв, а после сравниваю массив с полученными словами и массив слов из словаря и считаю сколько совпадений. Но для этого надо получить все возможные варианты слов.
D_Gon
 Аватар для D_Gon
22 / 11 / 5
Регистрация: 09.07.2015
Сообщений: 47
11.07.2015, 20:06     Комбинаторика. Вывести все слова, которые можно составить из данных букв #4
20*19*...*10*9*8
Комбинаций 482.718.652.416.000 ~ 5*10^14
Частота моего процессора 3,1ГГц ~ 3*10^9
Пусть процессор составляет слово за 1 такт
Тогда мне нужно ( 5*10^14 )/( 3*10^9 ) секунд ~ 1.5*10^5 ~ 43 часа
Вывести на консоль гораздо дольше.
S_el
1908 / 1503 / 296
Регистрация: 15.12.2013
Сообщений: 5,920
11.07.2015, 20:12     Комбинаторика. Вывести все слова, которые можно составить из данных букв #5
Цитата Сообщение от Leonman Посмотреть сообщение
Вывести все слова, которые можно составить из данных букв, длинна слова соответственно тоже дана.
Проще словарь перебрать на совпадение.Так оно намного быстрее будет.
Excalibur921
426 / 235 / 37
Регистрация: 12.10.2013
Сообщений: 1,796
11.07.2015, 20:17     Комбинаторика. Вывести все слова, которые можно составить из данных букв #6
Цитата Сообщение от Leonman Посмотреть сообщение
Вывести все слова, которые можно составить из данных букв, длинна слова соответственно тоже дана.
Комп может переставлять буквы хаотически это будут слова со значением? Нет… значит нет другого способа как создавать огромную базу данных по типу слова длинной 3 буквы))) из таких букв потом из таких…
Разве может быть альтернатива? А если просто переставлять буквы будет абракадабра для человека но не для алгоритма, А потом искать опять по огромной базе существует ли такое слово у человеков. А сленг?
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
11.07.2015, 20:18  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #7
S_el, так мне же его надо переберать, когда мне есть с чем сравнивать(тоесть санчала надо получить возможные варианты) или что вы имеете ввиду?
ampermetr
16 / 16 / 8
Регистрация: 01.05.2015
Сообщений: 145
11.07.2015, 20:23     Комбинаторика. Вывести все слова, которые можно составить из данных букв #8
Leonman, я бы сделал наоборот - разбил бы орфографический словарь на 30 (или 31, не уверен есть ли слова, начинающиеся на Ы) файл. К примеру искомое слово содержит 10 букв, значит нужно перебрать варианты всего из 10 файлов. Потом отсеиваем слова, не содержащие заданных букв, и в конце отсеиваем слова длиннее 10 букв. Мне кажется так будет намного быстрее.
Excalibur921
426 / 235 / 37
Регистрация: 12.10.2013
Сообщений: 1,796
11.07.2015, 20:45     Комбинаторика. Вывести все слова, которые можно составить из данных букв #9
А зачем сортировать каждый раз если достаточно сделать базу данных 1 раз. В итоге на вход будет 2 числа, применяемые буквы и их количество. Сначала отсканить словарик, потом проанализировать на количество букв и какие буквы использованы.
И будет мгновенный результат без поиска каждый раз.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
11.07.2015, 20:54  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #10
ampermetr, вариант, попробую.

Добавлено через 4 минуты
Excalibur921, данные на вход подаются в такой формате:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
5 a i n n v o x z
10 g o l a u r r c t d s o i i e h
4 o o m s q u c
13 i r a l e n n g o g m m y n e r v t i i
8 x e c l r k z d s e u p o
12 c e l e k b s s c o c a l z j i k t l
3 a t p z a
11 h k a e b b t u n f i q i l a n m
10 a e c s e d g r o s v d e p w m
9 e g a j t r b k r m s t o i
8 e l l a l a b b c c r y u
10 b a e e u s t i f u w a j d u i
4 o r s w m m g
где первое число, длина слова, а далее буквы из которых надо составить это слово/слова
Excalibur921
426 / 235 / 37
Регистрация: 12.10.2013
Сообщений: 1,796
11.07.2015, 21:03     Комбинаторика. Вывести все слова, которые можно составить из данных букв #11
Цитата Сообщение от Leonman Посмотреть сообщение
ampermetr, вариант,
И будет система с
Цитата Сообщение от Leonman Посмотреть сообщение
но все они работают очень долго,
Потому как скорей всего такой подход там и есть в виду простоты и очевидности. Время на поиск и сортировку и идет =).

Добавлено через 8 минут
Цитата Сообщение от Leonman Посмотреть сообщение
10 a e c s e d g r o s v d e p w m
А где сортировка по алфавиту + если две буквы? Наверно быстрей чем я предложил метода не существует, т.к это уже все возможные решения. В итоге длинна слова и буквы превращаются в одно число просто указатель на фаил какие слова вывести…Вам же нужна имена скорость? Ну вот… один такт))).Только вот база наверно страшная… И предварительное ее создание долго.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11843 / 6822 / 771
Регистрация: 27.09.2012
Сообщений: 16,915
Записей в блоге: 2
Завершенные тесты: 1
11.07.2015, 21:06     Комбинаторика. Вывести все слова, которые можно составить из данных букв #12
Качаем словарь. Сортируем в нем все слова по длине (можно и по алфавиту, чтобы еще эффективнее искать потом). Всё, наш словарь готов.
В проге, при загрузке, запоминаем где в словаре начинаются слова определенной длины(можно это указать в начале файла или в отдельном файле с конфигом). Попалось слово из 7 букв? Пожалуйста, идем по необходимому смещению и уже отсюда начинаем все слова сравнивать по маске. Есть совпадение? Запоминаем слово и ищем дальше. И в таком темпе пока не дойдем до смещения, соответствующего словам с длиной 8 символов. Можно организовать добавление слов в словарь и т.д.
Excalibur921
426 / 235 / 37
Регистрация: 12.10.2013
Сообщений: 1,796
11.07.2015, 21:34     Комбинаторика. Вывести все слова, которые можно составить из данных букв #13
Цитата Сообщение от Croessmah Посмотреть сообщение
Запоминаем слово и ищем дальше. И в таком темпе
Цитата Сообщение от Excalibur921 Посмотреть сообщение
И будет система с
Цитата Originally Posted by Leonman View Post
но все они работают очень долго,
Вот простая аналогия отбалды:
Что вы хотите ТС?
1)База данных 500 гиг вводите вопрос сразу ответ.
2)База данных 10 гиг ждете 30 минут ответ.
Ваш выбор?
Метод что я привел можно только ухудшать =).

Добавлено через 14 минут
А вообще наверно аналогия сильно не правильная. В словарике каждое слово уникально. Значит размер базы данных не может быть больше самого словаря. А тормазность ответа именно в не желании создавать базу данных ответов что я описал.
Значит выбор такой
1) искать в словарике разбитом на куски и ждать
2) получить готовый ответ предварительно перемолов все варианты и создав базу данных ответов.
S_el
1908 / 1503 / 296
Регистрация: 15.12.2013
Сообщений: 5,920
11.07.2015, 21:37     Комбинаторика. Вывести все слова, которые можно составить из данных букв #14
Цитата Сообщение от Leonman Посмотреть сообщение
так мне же его надо переберать, когда мне есть с чем сравнивать
считали слово,отсортировали и проверяете его наличие в отсортированном словаре.

P.S Сам словарь в каком виде и где хранится?
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
11.07.2015, 22:59  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #15
Цитата Сообщение от Croessmah Посмотреть сообщение
Пожалуйста, идем по необходимому смещению и уже отсюда начинаем все слова сравнивать по маске.
ну тоесть вы все равно предлогаете использовать размещение или я опять не правильно понял. У меня один вопрос, как получить все слова, чтоб я мог сравнивать с отсортированным массивом?

Добавлено через 55 секунд
Цитата Сообщение от S_el Посмотреть сообщение
считали слово,отсортировали
, так откуда его считывать то? Словарь храниться в .txt

Добавлено через 2 минуты
Возможно я некорректно/непонятно объяснил задание.
вот такая строчка на вход:
C++
1
5 a i n n v o x z
значит, что я должен на выход предоставить количество слов, длинна которых 5 знаков, которые состоят из вот этих букв:
C++
1
a i n n v o x z
+ чтоб это слово существовало в природе
S_el
1908 / 1503 / 296
Регистрация: 15.12.2013
Сообщений: 5,920
12.07.2015, 00:00     Комбинаторика. Вывести все слова, которые можно составить из данных букв #16
Цитата Сообщение от Leonman Посмотреть сообщение
так откуда его считывать то?
Оттуда где у вас храниться эти вот данные.

Цитата Сообщение от Leonman Посмотреть сообщение
чтоб это слово существовало в природе
т.е. в словаре.В природе может существовать любое слово,составленное из этих букв.И для определения количества вам даже считывать словарь не придется,просто использовать комбинаторику
Давайте,чтобы не быть голословными, опробуем способ на реальных данных.Прикрепите файл-словарь и файл входных данных.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 00:08  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #17
S_el, Так и не понял, что вы хотите сделать, однако вот:
входные: InputData.txt
словарь: _AllWords.rar (пришлось заарфивить, по размеру не проходил)
S_el
1908 / 1503 / 296
Регистрация: 15.12.2013
Сообщений: 5,920
12.07.2015, 00:23     Комбинаторика. Вывести все слова, которые можно составить из данных букв #18
Leonman, мне б желательно такой,чтобы можно было понять работает или нет.А пока буду думать
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 00:31  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #19
S_el, могу прикрепить файл, что должно получиться на выходе, надо?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2015, 00:37     Комбинаторика. Вывести все слова, которые можно составить из данных букв
Еще ссылки по теме:

Удалить из текста все слова, которые начинаются с букв, заданных в строке запроса C++
Найти в файле все слова, которые можно сложить из букв заданного слова C++
C++ Вывести те слова из текста на экран, которые отсортированы по количеству гласных букв

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
S_el
1908 / 1503 / 296
Регистрация: 15.12.2013
Сообщений: 5,920
12.07.2015, 00:37     Комбинаторика. Вывести все слова, которые можно составить из данных букв #20
Leonman, надо.
Yandex
Объявления
12.07.2015, 00:37     Комбинаторика. Вывести все слова, которые можно составить из данных букв
Ответ Создать тему
Опции темы

Текущее время: 12:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru