Форум программистов, компьютерный форум 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++ Определить, можно ли из букв одного слова составить другое
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 00:50  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #21
S_el, Сорри, с предыдущим input`ом не вышло, вот новый input:Input.txt и output:Output.txt
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
S_el
1906 / 1501 / 295
Регистрация: 15.12.2013
Сообщений: 5,912
12.07.2015, 01:35     Комбинаторика. Вывести все слова, которые можно составить из данных букв #22
Leonman, представление входного файла изменять можно?
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 01:45  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #23
S_el, нет, входные данные всегда подоются в таком формат. а Зачем енять формат?
S_el
1906 / 1501 / 295
Регистрация: 15.12.2013
Сообщений: 5,912
12.07.2015, 01:47     Комбинаторика. Вывести все слова, которые можно составить из данных букв #24
Это я к чему спросил,если убрать пробелы между буквами,тогда можно сделать так:
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 побуквенно или считывайте построчно и проводите разбор строки). Лично мне проще модифицировать файл.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 02:05  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #25
S_el, спасибо за вариант, завтра попробую разобрать, так как не знаком с библиотекой unordered_map
S_el
1906 / 1501 / 295
Регистрация: 15.12.2013
Сообщений: 5,912
12.07.2015, 02:09     Комбинаторика. Вывести все слова, которые можно составить из данных букв #26
Цитата Сообщение от Leonman Посмотреть сообщение
так как не знаком с библиотекой unordered_map
Это не библиотека,а заголовочный файл стандартной библиотеки C++11.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 02:14  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #27
S_el, а почему он подключается как библиотека?
S_el
1906 / 1501 / 295
Регистрация: 15.12.2013
Сообщений: 5,912
12.07.2015, 02:25     Комбинаторика. Вывести все слова, которые можно составить из данных букв #28
Цитата Сообщение от Leonman Посмотреть сообщение
а почему он подключается как библиотека?
Вы не так поняли.Библиотека может содержать несколько заголовочных файлов,которые подключаются отдельно.А заголовочный файл содержит в себе компоненты,специально разделенные, для повышения эффективности и удобства работы.
Более подробную и точную информацию читайте в литературе или статьях, например на той-же википедии:
https://ru.wikipedia.org/wiki/%D0%97...B0%D0%B9%D0%BB
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
12.07.2015, 13:01     Комбинаторика. Вывести все слова, которые можно составить из данных букв #29
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");
}
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 15:02  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #30
Mr.X, Спасибо за вариант. Хотя, конечно для моего уровня знаний, разобрать такой код представляет приличную сложность. Однако спасибо.
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
12.07.2015, 15:31     Комбинаторика. Вывести все слова, которые можно составить из данных букв #31
Цитата Сообщение от Leonman Посмотреть сообщение
Хотя, конечно для моего уровня знаний, разобрать такой код представляет приличную сложность.
Ну, STL заодно подучите. Там только мэпы и множества надо знать, ну и алгоритм includes.
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 16:39  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #32
Mr.X, а почему вы используете так много typedef`ов, на string, на vector, на map? Так требует делать хороший тон программирования или просто вам так удобнее? Потому что для меня например, читаемость кода сильно падает.
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
12.07.2015, 16:45     Комбинаторика. Вывести все слова, которые можно составить из данных букв #33
Цитата Сообщение от Leonman Посмотреть сообщение
Mr.X, а почему вы используете так много typedef`ов, на string, на vector, на map? Так требует делать хороший тон программирования или просто вам так удобнее? Потому что для меня например, читаемость кода сильно падает.
Ну, специалисты советуют именовать типы не в контексте языка программирования, а в контексте решаемой задачи. Так что для понятности и читаемости кода это и делается. Мэпы я именую по определенной системе. Если вы ее поймете, то все сразу станет ясно. Я наоборот поражаюсь, когда вижу, как некоторые люди трехэтажные типы мэпов именуют непосредственно. Никогда не понимал как они потом сами это читают.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2015, 16:58     Комбинаторика. Вывести все слова, которые можно составить из данных букв
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Leonman
 Аватар для Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 16:58  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #34
Mr.X, спасибо.
Yandex
Объявления
12.07.2015, 16:58     Комбинаторика. Вывести все слова, которые можно составить из данных букв
Ответ Создать тему
Опции темы

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