Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.61/41: Рейтинг темы: голосов - 41, средняя оценка - 4.61
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274

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

11.07.2015, 18:54. Показов 9079. Ответов 33
Метки нет (Все метки)

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

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

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

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

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

Спасибо за внимание.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
11.07.2015, 18:54
Ответы с готовыми решениями:

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

Дано слово р и файл f. Найти в файле f все слова, которые можно составить из букв слова р
Дано слово р и файл f. Найти в файле f все слова, которые можно составить из букв слова р.

Вывести в алфавитном порядке все слова, содержащие наибольшее количество гласных букв; найти все слова, в которые буква
Вывести в алфавитном порядке все слова, содержащие наибольшее количество гласных букв; найти все слова, в которые буква «а» входит не менее...

33
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.07.2015, 00:50  [ТС]
Студворк — интернет-сервис помощи студентам
S_el, Сорри, с предыдущим input`ом не вышло, вот новый input:Input.txt и output:Output.txt
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
12.07.2015, 01:35
Leonman, представление входного файла изменять можно?
0
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.07.2015, 01:45  [ТС]
S_el, нет, входные данные всегда подоются в таком формат. а Зачем енять формат?
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
12.07.2015, 01:47
Это я к чему спросил,если убрать пробелы между буквами,тогда можно сделать так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# include <iostream>
# include <fstream>
# include <unordered_map>
# include <algorithm>
# include <string>
 
bool can_create(const std::string &key,std::string string);
int main()
    {
    std::string line;
    std::unordered_map<size_t,std::unordered_map<std::string,size_t>> Dict;
    std::ifstream myfile("_AllWords.txt");
    std::ofstream out("QW2.txt");
    if(myfile.is_open())
        {
        while (std::getline(myfile,line))
            {
            std::sort(line.begin(),line.end());
            Dict[line.size()][line]++;
            }
        myfile.close();
        }
    else 
        std::cout << "Couldn't open file!" << std::endl;
    myfile.open("i1.txt");
 
    if(myfile)
        {
        while (true)
            {
            size_t N,M;
            std::string test;
            myfile>>N;
            myfile>>test;
            if(!myfile) break;
            M = test.size();
            size_t total=0;
            for(const auto &el:Dict[N])
                {
                if(can_create(el.first,test))
                    total+=el.second;
                }
            out<<total<<std::endl;
            }
        myfile.close();
        }
    else 
        std::cout << "Couldn't open file!" << std::endl;
 
    out.close();
    return 0;
    }
 
bool can_create(const std::string &key,std::string string)
    {
    size_t count=0;
    for(const auto &el : key)
        {
        size_t pos = string.find(el);
        if(pos!=std::string::npos)
            {
            string.erase(pos,1);
            count++;
            }
        }
    return count==key.size();
    }
Добавлено через 1 минуту
Цитата Сообщение от Leonman Посмотреть сообщение
нет, входные данные всегда подоются в таком формат. а Зачем енять формат?
тогда измените приведенный выше код,под нужный вам формат(наращивайте std::string побуквенно или считывайте построчно и проводите разбор строки). Лично мне проще модифицировать файл.
1
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.07.2015, 02:05  [ТС]
S_el, спасибо за вариант, завтра попробую разобрать, так как не знаком с библиотекой unordered_map
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
12.07.2015, 02:09
Цитата Сообщение от Leonman Посмотреть сообщение
так как не знаком с библиотекой unordered_map
Это не библиотека,а заголовочный файл стандартной библиотеки C++11.
0
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.07.2015, 02:14  [ТС]
S_el, а почему он подключается как библиотека?
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
12.07.2015, 02:25
Цитата Сообщение от Leonman Посмотреть сообщение
а почему он подключается как библиотека?
Вы не так поняли.Библиотека может содержать несколько заголовочных файлов,которые подключаются отдельно.А заголовочный файл содержит в себе компоненты,специально разделенные, для повышения эффективности и удобства работы.
Более подробную и точную информацию читайте в литературе или статьях, например на той-же википедии:
https://ru.wikipedia.org/wiki/... 0%B9%D0%BB
1
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
12.07.2015, 13:01
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
/////////////////////////////////////////////////////////////////////////////////////////
//Подсчитать все слова из заданного словаря, которые можно составить из данных букв, 
//длинна слова соответственно тоже дана.
//
//ВХОДНОЙ ФАЙЛ (где первое число, длина слова, а далее буквы из которых надо составить это слово/слова):
/*
//17
13 p l g l t o i b b a n a n h z t i s f e
9 e s s a s t s i l m e r a k
6 o r l b s k o i d l
8 p o s s b c d a e d d t l
7 l e r i e l o i w a b
10 i e o e i n b f l l x i y u i j
5 h n m m i b d s
10 n o v o i v i z o l n i r r a t
6 b l e v n e k b i s
5 n s h e a r s c
6 l s z a b v h y i y
10 s e d e i t w c u i a m a t a r
5 u q d t b r s s
8 n n e g t l n i s g e x z
11 r b t w e c o m a m i e z d y z u
7 y s t h y o k a e r e
7 e g y z d y v a o u z
*/
//
//ВЫХОДНОЙ ФАЙЛ:
/*
1 4 6 7 6 2 3 2 15 33 2 8 9 11 1 6 1 
*/
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                                                                 T_str;
typedef T_str                                                                       T_word;
 
typedef std::multiset   < char                                                  >   T_letters_set;
typedef T_letters_set                                                               T_word_letters_set;
typedef T_letters_set                                                               T_pattern_letters_set;
 
typedef int                                                                         T_word_size;
typedef std::pair       < T_word_size,          T_pattern_letters_set           >   T_pattern;
typedef std::vector     < T_pattern                                             >   T_patterns;
 
typedef std::map        < T_word_letters_set,   int                             >   T_count_of_word_letters_set;
typedef std::map        < T_word_size,          T_count_of_word_letters_set     >   T_dictionary;
/////////////////////////////////////////////////////////////////////////////////////////
T_letters_set    get_letters_set_of_word( T_word  const   &   word )
{
    T_letters_set    res_letset;
 
    std::copy
        (
            word.begin  (),
            word.end    (),
 
            std::inserter
                (
                    res_letset,
                    res_letset.begin()
                )
        );
 
    return  res_letset;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_from_file_with_name_input_dictionary
    (
        T_str           const   &   dictionary_filename,
        T_dictionary            &   dictionary
    )
{
    std::ifstream   ifile( dictionary_filename );
 
    bool    bool_res    =   ifile   !=  nullptr;
 
    if( bool_res )
    {
        T_word  word_cur;
 
        while( ifile >> word_cur )
        {
            ++dictionary
                [
                    word_cur.size()
                ]
                [
                    get_letters_set_of_word( word_cur )
                ];
        }
    }//if
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
bool    successfully_from_file_with_name_input_patterns
    (
        T_str       const   &   patterns_filename,
        T_patterns          &   patterns
    )
{
    std::ifstream   ifile( patterns_filename );
 
    bool    bool_res    =   ifile   !=  nullptr;
 
    if( bool_res )
    {
        int     patterns_count  =   0;
        ifile   >>  patterns_count;
 
        for( int  i = 0; i < patterns_count; ++i )
        {
            int     word_size   =   0;
            T_word  pattern_word;
 
            ifile   >>  word_size;
 
            std::getline
                (
                    ifile,
                    pattern_word
                );
 
            patterns.push_back
                (
                    T_pattern
                        (
                            word_size,
                            get_letters_set_of_word( pattern_word )
                        )
                );
        }//for
    }//if
 
    return  bool_res;
}
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_count_words_for_pattern_in
{
    //-----------------------------------------------------------------------------------
    const   T_dictionary  &   dictionary_;
    //-----------------------------------------------------------------------------------
    T_count_words_for_pattern_in( T_dictionary    const   &   dictionary )
        :
        dictionary_ ( dictionary )
    {}
    //-----------------------------------------------------------------------------------
    int     operator()  ( T_pattern     const   &   pattern )
    {
        int     word_counter                                =   0;
        auto    word_size_and_count_of_word_letters_set_it  =   dictionary_.find( pattern.first );
 
        if  (
                word_size_and_count_of_word_letters_set_it  !=  dictionary_.end()
            )
        {
            auto    &   count_of_word_letters_set   =   word_size_and_count_of_word_letters_set_it->second;
 
            for (
                    auto
                    word_letters_set_and_count_it   =   count_of_word_letters_set.begin     ();
                    word_letters_set_and_count_it   !=  count_of_word_letters_set.end       ();
                    ++word_letters_set_and_count_it
                )
            {
                if  (
                        std::includes
                            (
                                pattern.second                          .begin  (),
                                pattern.second                          .end    (),
 
                                word_letters_set_and_count_it->first    .begin  (),
                                word_letters_set_and_count_it->first    .end    ()
                            )
                    )
                {
                    word_counter    +=  word_letters_set_and_count_it->second;
                }//if
            }//for
        }//if
 
        return  word_counter;
    }
    //-----------------------------------------------------------------------------------   
};
/////////////////////////////////////////////////////////////////////////////////////////
void    count_words_in_dictionary_for_patterns_and_output_in_file_with_name
    (
        T_dictionary    const   &   dictionary,
        T_patterns      const   &   patterns,
        T_str           const   &   word_counts_filename
    )
{
    std::ofstream   ofile( word_counts_filename );
 
    std::transform
        (
            patterns.begin                  (),
            patterns.end                    (),
            std::ostream_iterator<int>      ( ofile, " "    ),
            T_count_words_for_pattern_in    ( dictionary    )
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
    const   T_str   DICTIONARY_FILENAME     =   "all_words.txt";
    const   T_str   PATTERNS_FILENAME       =   "input.txt";
    const   T_str   WORD_COUNTS_FILENAME    =   "output.txt";//
 
    T_dictionary    dictionary;
    T_patterns      patterns;
 
    if  (
                successfully_from_file_with_name_input_dictionary
                    (
                        DICTIONARY_FILENAME,
                        dictionary
                    )
 
            &&  successfully_from_file_with_name_input_patterns
                    (
                        PATTERNS_FILENAME,
                        patterns
                    )
        )
    {
        std::cout   <<  "Данные загружены."
                    <<  std::endl;
 
        count_words_in_dictionary_for_patterns_and_output_in_file_with_name
            (
                dictionary,
                patterns,
                WORD_COUNTS_FILENAME
            );
 
        std::cout   <<  "Слова подсчитаны."
                    <<  std::endl;
    }
    else
    {
        std::cout   <<  "Невозможно прочитать данные из входных файлов."
                    <<  std::endl;
    }
 
    system("pause");
}
1
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.07.2015, 15:02  [ТС]
Mr.X, Спасибо за вариант. Хотя, конечно для моего уровня знаний, разобрать такой код представляет приличную сложность. Однако спасибо.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
12.07.2015, 15:31
Цитата Сообщение от Leonman Посмотреть сообщение
Хотя, конечно для моего уровня знаний, разобрать такой код представляет приличную сложность.
Ну, STL заодно подучите. Там только мэпы и множества надо знать, ну и алгоритм includes.
0
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.07.2015, 16:39  [ТС]
Mr.X, а почему вы используете так много typedef`ов, на string, на vector, на map? Так требует делать хороший тон программирования или просто вам так удобнее? Потому что для меня например, читаемость кода сильно падает.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
12.07.2015, 16:45
Цитата Сообщение от Leonman Посмотреть сообщение
Mr.X, а почему вы используете так много typedef`ов, на string, на vector, на map? Так требует делать хороший тон программирования или просто вам так удобнее? Потому что для меня например, читаемость кода сильно падает.
Ну, специалисты советуют именовать типы не в контексте языка программирования, а в контексте решаемой задачи. Так что для понятности и читаемости кода это и делается. Мэпы я именую по определенной системе. Если вы ее поймете, то все сразу станет ясно. Я наоборот поражаюсь, когда вижу, как некоторые люди трехэтажные типы мэпов именуют непосредственно. Никогда не понимал как они потом сами это читают.
1
 Аватар для Leonman
15 / 15 / 4
Регистрация: 17.06.2012
Сообщений: 274
12.07.2015, 16:58  [ТС]
Mr.X, спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
12.07.2015, 16:58

Найти в файле f все слова, которые можно сложить из букв слова р
Дано слово р и файл f.найти в файле f все слова которые можна сложить с букв слова р. ФАЙЛ ТЕКСТОВЫЙ! там надо указать путь и тд и тп

Найти в файле все слова, которые можно сложить из букв заданного слова
Дано слово р и файл f.найти в файле f все слова которые можна сложить с букв слова р.

Вывести все слова текста, которые нельзя составить из «ключевого» слова
Помогите пожалуйста,в edit1 вводиться текст нужно вывести все слова текста, которые нельзя составить из «ключевого» слова. Ключевое слово...

Вывести на экран все слова, которые имеют парное количество букв
Помогите пожалуйста решить задачу, очень прошу: Розробити програму що виводить на екран вси слова ,яки мають парну килькисть букв. ...

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


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

Или воспользуйтесь поиском по форуму:
34
Ответ Создать тему
Новые блоги и статьи
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
Установка MinGW GCC 16.2 и CMake
8Observer8 10.08.2026
VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия
Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо
anaschu 10.08.2026
Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства
russiannick 07.08.2026
1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь
Мир по моей воле
kumehtar 07.08.2026
Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор
Maks 05.08.2026
Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .
У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35".
kumehtar 04.08.2026
С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru