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

Поиск анаграмм - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 40, средняя оценка - 4.73
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
16.10.2011, 02:01     Поиск анаграмм #1
Доброй ночи!
Такая задачка... Возможно многим знакома по Золотому байту. Я в самом начале изучения С++ и до конца не могу разобраться.
Есть файл "in.txt" с каким-либо списком слов (до 10000). Одна строка - одно слово.
Нужно найти все анаграммы и вывести их в файл "out.txt".
Например во входном файле:
kot
polet
tok
leto
teplo
kto
zima

Тогда на выходе:
kot
tok
kto
polet
teplo

Примерно так...
Во время первого считывания файла я определяю кол-во строк. Затем создаю массив строк.
Далее сортирую буквы в словах.
Это сделал. Вроде и дальше понимаю путь (с помощью strcmp ищем дубликаты). Но на деле не получается. Не пойму , как обратно отсортировать. Или какой другой алгоритм нужен. И как в файл записать... Классы не использовать.
Посмотрите код и помогите пожалуйста.
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
#include<iostream>
#include <cstdlib>
#include<stdio.h>
#include <iomanip>
#include<cctype>
#include<cstring>
using namespace std;
void BubbleSort1(char[],int);
int main()
{
    setlocale(LC_ALL,"rus");
    FILE *file;
    char str[255];
    int N,M=0;
    if((file=fopen("in.txt", "r"))!=NULL)
    {
    do
        {
            fgets(str,255,file);
            M++;
        } while(!feof(file));
        fclose(file);
    }
    else
    {
        cout<<"File not found"<<endl;
    }
    char **mas = new char*[M];
    for(int i=0;i<M;i++)
    {
        mas[i]=new char[255];
    }
    if((file=fopen("in.txt", "r"))!=NULL)
    {
        for(int i=0;i<M;i++)
        {
            fgets(mas[i],255,file);
        }
        fclose(file);
    }
    else
    {
        cout<<"Error";
    }
    for(int i=0;i<M;i++)
    {
        cout<<mas[i];
    }
    cout<<"\n\n";
    for(int i=0;i<M;i++)
    {
        N=strlen(mas[i]);
        BubbleSort1(mas[i],N);
    }
    for(int i=0; i<M-1; i++)
    {
        cout<<mas[i];
    }
    cout<<"\n\n";
    for(int i=0;i<M;i++)
    {
        char*y=mas[i];
        for(int j=i+1;j<M;j++)
        {
            if(strcmp(y,mas[j])==0)
            {
                cout<<y;
            }
        }
    }
    cout<<endl;
    system("pause");
    return 0;
}
void BubbleSort1(char*mas,int M)
{
    bool sort=true;
    while(sort)
    {
        sort=false;
        for(int i=0;i<M-1;i++)
        {
            if(mas[i]>mas[i+1])
            {
                int x=mas[i];
                mas[i]=mas[i+1];
                mas[i+1]=x;
                sort=true;
            }
        }
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
16.10.2011, 04:29     Поиск анаграмм #2
если вы ограничены только нижним регистром и точно знаете что отсутствуют цифры и знаки препинания то не надо сортировать, ищите совпадения по суммам символов. но помните что сумма это еще не не анаграмма, например "no" == "ex" == 221. вот идея
C
1
2
3
4
while(i != strlen(str))
    sum +=str[i];
while(fgets(buf, 255, filename) != eof)
      anagram = check(sum, buf, str);
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
16.10.2011, 08:52  [ТС]     Поиск анаграмм #3
Цитата Сообщение от alkagolik Посмотреть сообщение
если вы ограничены только нижним регистром и точно знаете что отсутствуют цифры и знаки препинания то не надо сортировать, ищите совпадения по суммам символов. но помните что сумма это еще не не анаграмма, например "no" == "ex" == 221. вот идея
C
1
2
3
4
while(i != strlen(str))
    sum +=str[i];
while(fgets(buf, 255, filename) != eof)
      anagram = check(sum, buf, str);
Оригинально...
А можно эту идею на каком-нибудь небольшом примере показать, пожалуйста...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.10.2011, 08:56     Поиск анаграмм #4
Вместо кодов символов можно суммировать коды из хэш таблицы. Меньше ложных совпадений будет. И заглавные буквы можно будет "приравнять" к строчным.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
16.10.2011, 09:39     Поиск анаграмм #5
slavik, дайте входной файл потестировать
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
16.10.2011, 09:54  [ТС]     Поиск анаграмм #6
Файл может быть с разным кол-вом слов. До 10000.
Поэтому и нужен первый пробег по файлу для выяснения кол-ва строк.
Цифры, пробелы, знаки препинания отсутствуют. Только буквы.
Ну например такой:
Вложения
Тип файла: txt in.txt (121 байт, 38 просмотров)
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.10.2011, 13:19     Поиск анаграмм #7
Вот, решил через связность. Алгоритм, конечно, жуткий и жадный на память и ресурсы, но что придумал.

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
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
 
/* определяет равенство строк по количеству вхождений каждой *
 * буквы в эту строку. пробелы цифры и пр. игнорируются      */
bool letter_cmp( const std::string &a, const std::string &b )
{
    unsigned count_a[ 'z' - 'a' + 1 ] = {0}; // количество вхождений букв в строку а
    unsigned count_b[ 'z' - 'a' + 1 ] = {0}; // количество вхождений букв в строку b
 
    // считаем a
    for( int i = 0; i < a.size(); i++ )
    {
        if( isalpha( a[i] ) )
           count_a[ 'z' - tolower( a[i] ) ]++;
    }
 
    // считаем b
    for( int i = 0; i < b.size(); i++ )
    {
        if( isalpha( b[i] ) )
           count_b[ 'z' - tolower( b[i] ) ]++;
    }
 
    // проверяем равенство вхождений каждой буквы
    for( int i = 0; i < 'z' - 'a'; i++ )
    {
        if( count_a[i] != count_b[i] )
           return false; // если количество вхождений этой буквы отличается, возвращаем false
    }
 
    return true; // если все вхождения равны, возвращаем true
}
 
int main()
{
    std::vector<std::string> lines; // здесь хранятся строки файла
    std::string input; // сюда вводится новая строка из файла
 
    // ---------- читаем весь файл ---------
    std::ifstream fs( "in.txt" );
 
    if( !fs.is_open() )
    {
       std::cerr << "error opening in.txt\n";
       return -1;
    }
 
    while( fs >> input )
       lines.push_back( input );
 
    fs.close();
 
    std::cout << "done reading " << lines.size() << " words\n\n";
 
    // ---- заполняем вектор связности -----
    std::vector<int> connectivity( lines.size() );
 
    for( int i = 0; i < lines.size(); i++ )
       connectivity[i] = i;
 
    // ---- определяем связность -----------
 
    for( int i = 0; i < lines.size(); i++ ) // проходим все строки
    {
        for( int u = 0; u < lines.size(); u++ ) // n*n раз
        {
            if( connectivity[i] != connectivity[u] ) // если эти две строки уже связаны, пропускаем их
            {
                if( letter_cmp( lines[i], lines[u] ) ) // иначе если строки равны по количеству вхождений букв
                {
                    // связываем их
                    int old_i = connectivity[i]; // старое значение ключа
 
                    for( int j = 0; j < connectivity.size(); j++ )
                    {
                        if( connectivity[j] == old_i ) // везде, где ключ старый
                           connectivity[j] = connectivity[u]; // меняем его на новый
                    }
                }
            }
        }
    }
 
    // ---- выводим все связанные слова ------
    for( int i = 0; i < connectivity.size(); i++ )
    {
        unsigned int out = 0;
 
        if( std::count( connectivity.begin(), connectivity.end(), i ) > 1 )
        {
            for( int u = 0; u < connectivity.size(); u++ )
            {
               if( connectivity[u] == i )
               {
                  if( out )
                     std::cout << ", ";
 
                  std::cout << lines[u];
                  out++;
               }
            }
 
            if( out )
               std::cout << '\n';
        }
    }
 
    return 0;
}
Интересно было бы увидеть более красивое решение.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
16.10.2011, 13:32     Поиск анаграмм #8
у меня тоже чепуха какая-то, более того - из-за смены курсора в файле (строки 50, 70)не хочет завершать цикл
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
#include <stdio.h>
#include <stdlib.h>
 
char in(char * str, char *buf)
{
    int i = 0, j;
    char ch = 0;
    while(str[i])
    {
        j = 0; ch = 0;
        while (buf[j])
            if (str[i] == buf[j++])
            {
                ch = 1;
                break;
            }
        if (!ch)
            break;
        else
            ++i;
    }
    return ch;
}
 
int main ()
{
    char *buf, *str;
 
    buf = (char*)malloc(1 << 7);
    if (!buf)
        exit(-1);
 
    str = (char*)malloc(1 << 7);
    if (!str)
        exit(-1);
 
    int tmp = 0, i = 0, sum = 0;
    fpos_t pos;
 
    FILE *filename;
    filename = fopen("/home/chertopolox/downloads/in.txt", "r");
 
    if (!filename)
        exit(-2);
 
    while ( !feof(filename) )
    {
        fgets(str, 128, filename);
 
        fgetpos(filename, &pos);
 
        while (str[i] != '\0')
            sum ^= str[i++];
 
        while (!feof(filename))
        {
            fgets(buf, 128, filename);
 
            while (buf[i] != '\0')
                tmp ^= buf[i++];
 
            if ( sum == tmp )
                if ( in(str, buf) )
                    printf("%s == %s\n", str, buf);
 
            i = 0; tmp = 0;
        }
 
        i = 0; sum = 0;
        fsetpos(filename, &pos);
    }
    fclose(filename);
    free(str);
    free(buf);
    return 0;
}
KeyGen
 Аватар для KeyGen
333 / 289 / 6
Регистрация: 07.08.2011
Сообщений: 789
Записей в блоге: 1
16.10.2011, 13:33     Поиск анаграмм #9
Вот я писал только не для txt... Алгоритм работает...
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
#include <iostream>
 
using std::cout;
    
int main()
{
    setlocale(LC_ALL, "rus");
    
    char *p[10]={
         "int cool,",
         "float,",
         "double,",
         "short,",
         "int cool,",
         "char,",
         "float,",
         "int,",
         "int,",
         "short,"
         };
         
    char *ch[10];
    
         //Êîïèðóåì ñîäåðæГ*Г*ГЁГҐ Г¬Г*Г±Г±ГЁГўГ* *p
         for(int i=0; i<10; i++)
         ch[i]=p[i];
         
         int i=0;
         int schet=0;
         // ÓáåðГ*ГҐГ¬ ГЁГ§ Г¬Г*Г±Г±ГЁГўГ* ñòðîêè ГЎГҐГ§ ïîâòîðîâ
         while(i<10){
                    
                    for(int j=0; j<10; j++){
                    if(j==i)
                    continue;
                    if(strcmp(ch[i],ch[j]))
                    schet++;
                    }
                    if(schet==9)
                    {ch[i]="";schet=0;}
                    else
                    schet=0;
                    i++;
                 }            
         
         // ÓáåðГ*ГҐГ¬ ïîâòîðû
         i=0;
         while(i<10){
                    
                    for(int j=0; j<10; j++){
                    if(j==i)
                    continue;
                    if(!(strcmp(ch[j],ch[i])))
                    ch[j]="";
                    }
                    i++;
                 }           
         
         //Âûâîä Г¬Г*Г±Г±ГЁГўГ* *p
         cout << "Âåñü Г¬Г*Г±Г±ГЁГў:\n";
         for(int i=0; i<10; i++){
         cout << p[i] << " ";
         }
         
         //Âûâîä Г¬Г*Г±Г±ГЁГўГ* *ch
         cout << "\nÏîâòîðû:\n";
         for(int i=0; i<10; i++)
         if(ch[i]!="")
         cout << ch[i] << " ";
    
    
    
    cout << "\n\n\n";
    system("PAUSE");
    return 0;
}
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.10.2011, 13:35     Поиск анаграмм #10
Цитата Сообщение от talis Посмотреть сообщение
Интересно было бы увидеть более красивое решение.
Создаётся массив пар pair<string,string>. Вторым заносится слово, первым это же слово, но отсортированное по буквам без учёта регистра. Массив сортируется по первому в паре. Дальше всё очевидно.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.10.2011, 13:36     Поиск анаграмм #11
Ребят, ну через сумму решать - это же немного не то. 2 + 8 == 1 + 9 == 5 + 5 == 3 + 7 и так далее. Ошибки возможны

KeyGen, у вас, вроде, просто одинаковые строки ищет. А нужно-то анаграммы, то есть слова, которые состоят из одних и тех же букв: кот - ток - кто, и всё в этом роде.

Deviaphan, красиво
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
16.10.2011, 13:42     Поиск анаграмм #12
talis, я взял сложение по модулю чтобы избежать лишних проверок на вхождение, в случае эквивалентно, проверку на вхождение. Ну надо же уметь нестандартно мыслить Deviaphan давайте типа что ли тренинг на проявление смекалки а то я никак не мог увязать хеширование и задачу, а вон как надо
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.10.2011, 13:42     Поиск анаграмм #13
Deviaphan, стоп, а с учётом всех сортировок, не мыло ли будет?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.10.2011, 13:49     Поиск анаграмм #14
Цитата Сообщение от alkagolik Посмотреть сообщение
я никак не мог увязать хеширование и задачу
Уже увязал или пояснить? Поясню. Это чтобы суммировать не коды символов, а случайные цифры, чтобы меньше совпадений было. Или ксорить вместо суммирования.

Цитата Сообщение от talis Посмотреть сообщение
Ошибки возможны
Сумма как начальная проверка, оптимизация.

Цитата Сообщение от talis Посмотреть сообщение
стоп, а с учётом всех сортировок, не мыло ли будет?
Мыла не будет. Будет всё норм.
KeyGen
 Аватар для KeyGen
333 / 289 / 6
Регистрация: 07.08.2011
Сообщений: 789
Записей в блоге: 1
16.10.2011, 15:27     Поиск анаграмм #15
Цитата Сообщение от talis Посмотреть сообщение
KeyGen, у вас, вроде, просто одинаковые строки ищет. А нужно-то анаграммы, то есть слова, которые состоят из одних и тех же букв: кот - ток - кто, и всё в этом роде.
А если выровнять все слова по алфавиту и регистру, а потом сравнить. Вывод будет одно слово из анаграмм...
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
16.10.2011, 16:00  [ТС]     Поиск анаграмм #16
Непростая задача для меня, который программирование всего пару месяцев изучает.
Если даже у людей с опытом не все получается.

talis, код работает. А как его можно переделать, чтобы использовать using namespace std:
и чтобы в конце в файл записать? И еще - vector обязателен?
Мне главное понять, а не чтобы за меня написали. Да вот без примера понять не получается...
Может еще кто вариантов подкинет. Когда видишь код, то и понимание быстрее приходит.
Кстати, сделал входной файл на 50 слов.
Вложения
Тип файла: txt in.txt (391 байт, 17 просмотров)
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.10.2011, 16:05     Поиск анаграмм #17
slavik, вариант Deviaphan лучше, используйте его.

Добавлено через 49 секунд
vector - это, считайте, тот же массив, только саморасширяющийся. Можно без него, но зачем?
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
16.10.2011, 16:12  [ТС]     Поиск анаграмм #18
Цитата Сообщение от talis Посмотреть сообщение
slavik, вариант Deviaphan лучше, используйте его.
Еще бы понять, как его реализовать...
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.10.2011, 16:15     Поиск анаграмм #19
slavik, для сортировки используйте std::sort( начало_диапазона, конец_диапазона ). В случае с контейнерами STL (vector тот же) соответствующие итераторы можно получить через vec.begin() и vec.end(). А вообще, http://cplusplus.com/reference. Там есть поиск. Ищите std::string, std:: pair, std::sort и прочие.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.10.2011, 08:40     Поиск анаграмм
Еще ссылки по теме:

C++ Поиск символа не могу переделать под поиск сочетания символов
Поиск пикселя и поиск изображения на экране C++
Поиск числа в двумерном массиве (бинарный поиск) C++

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

Или воспользуйтесь поиском по форуму:
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
17.10.2011, 08:40  [ТС]     Поиск анаграмм #20
буду рыться...

Добавлено через 4 часа 4 минуты

бьюсь - не получается...
А можно доделать тот код программы, который я написал (см. в начале)?
Дело в том, что препод хотел именно так, хоть по другому и красивей.
Да и не учили мы еще всего остального.
А там я хоть алгоритм понимаю. С технической частью проблемы.
Люди, help...
Помогите написать работающий код...

Добавлено через 12 часов 9 минут
sos...sos...sos...
Yandex
Объявления
17.10.2011, 08:40     Поиск анаграмм
Ответ Создать тему
Опции темы

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