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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
#1

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

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

Всем привет.

Вобщем. Есть такая игра, в которой дают 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++
Можно ли из букв слова X составить слово Y? C++
C++ Вывести все слова текста, которые отличны от последнего слова, предварительно преобразовав их
C++ Определить, можно ли из букв одного слова составить другое
Определить сколько слов можно составить из букв прочитанного слова C++
Требуется найти слова, которые можно составить из данного C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
S_el
2092 / 1599 / 306
Регистрация: 15.12.2013
Сообщений: 6,427
12.07.2015, 00:00     Комбинаторика. Вывести все слова, которые можно составить из данных букв #16
Цитата Сообщение от Leonman Посмотреть сообщение
так откуда его считывать то?
Оттуда где у вас храниться эти вот данные.

Цитата Сообщение от Leonman Посмотреть сообщение
чтоб это слово существовало в природе
т.е. в словаре.В природе может существовать любое слово,составленное из этих букв.И для определения количества вам даже считывать словарь не придется,просто использовать комбинаторику
Давайте,чтобы не быть голословными, опробуем способ на реальных данных.Прикрепите файл-словарь и файл входных данных.
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 00:08  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #17
S_el, Так и не понял, что вы хотите сделать, однако вот:
входные: InputData.txt
словарь: _AllWords.rar (пришлось заарфивить, по размеру не проходил)
S_el
2092 / 1599 / 306
Регистрация: 15.12.2013
Сообщений: 6,427
12.07.2015, 00:23     Комбинаторика. Вывести все слова, которые можно составить из данных букв #18
Leonman, мне б желательно такой,чтобы можно было понять работает или нет.А пока буду думать
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 00:31  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #19
S_el, могу прикрепить файл, что должно получиться на выходе, надо?
S_el
2092 / 1599 / 306
Регистрация: 15.12.2013
Сообщений: 6,427
12.07.2015, 00:37     Комбинаторика. Вывести все слова, которые можно составить из данных букв #20
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
2092 / 1599 / 306
Регистрация: 15.12.2013
Сообщений: 6,427
12.07.2015, 01:35     Комбинаторика. Вывести все слова, которые можно составить из данных букв #22
Leonman, представление входного файла изменять можно?
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 01:45  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #23
S_el, нет, входные данные всегда подоются в таком формат. а Зачем енять формат?
S_el
2092 / 1599 / 306
Регистрация: 15.12.2013
Сообщений: 6,427
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
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 02:05  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #25
S_el, спасибо за вариант, завтра попробую разобрать, так как не знаком с библиотекой unordered_map
S_el
2092 / 1599 / 306
Регистрация: 15.12.2013
Сообщений: 6,427
12.07.2015, 02:09     Комбинаторика. Вывести все слова, которые можно составить из данных букв #26
Цитата Сообщение от Leonman Посмотреть сообщение
так как не знаком с библиотекой unordered_map
Это не библиотека,а заголовочный файл стандартной библиотеки C++11.
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 266
12.07.2015, 02:14  [ТС]     Комбинаторика. Вывести все слова, которые можно составить из данных букв #27
S_el, а почему он подключается как библиотека?
S_el
2092 / 1599 / 306
Регистрация: 15.12.2013
Сообщений: 6,427
12.07.2015, 02:25     Комбинаторика. Вывести все слова, которые можно составить из данных букв #28
Цитата Сообщение от Leonman Посмотреть сообщение
а почему он подключается как библиотека?
Вы не так поняли.Библиотека может содержать несколько заголовочных файлов,которые подключаются отдельно.А заголовочный файл содержит в себе компоненты,специально разделенные, для повышения эффективности и удобства работы.
Более подробную и точную информацию читайте в литературе или статьях, например на той-же википедии:
https://ru.wikipedia.org/wiki/%D0%97...B0%D0%B9%D0%BB
Mr.X
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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");
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2015, 15:02     Комбинаторика. Вывести все слова, которые можно составить из данных букв
Еще ссылки по теме:
C++ Работа из строками. Удалить все слова, которые начинаются с согласных букв
C++ Вывести только те слова сообщения, которые содержат не более чем n букв
C++ Вывести те слова из текста на экран, которые отсортированы по количеству гласных букв
Вывести только те слова сообщения, которые содержат не более чем n букв C++
Удалить из текста все слова, которые начинаются с букв, заданных в строке запроса C++

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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru