Задается словарь. Найти в нем все анаграммы

@curtis65 · Регистрация: 14.04.2013

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

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

Помогите!!

@gazlan · 16.04.2013, 04:20

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

Самый простой и быстрый вариант - это испортить словарь: отсортировать внутри каждого слова все буквы по алфавиту, а затем сами слова по по алфавиту. Остальное тривиально.

Если словарь портить нельзя...

Слова с разным количеством букв анаграммами быть не могут - проверяете только слова одинакового размера. Для каждого слова создаете массив счетчиков букв (33, если не различать регистр). Если для двух слов состояния счетчиков букв совпали - они являются анаграммой.

Проходите в цикле по списку слов (словарю) и за квадратичное время находите все анаграммы.

Если словарь предварительно отсортировать по размеру и по алфавиту, то будет быстрее :-)

Как (эквивалентный) вариант, можно выбрать систему счисления с (основание) > (число букв) и (основание) > (максимальная длина слова) и присвоить каждой букве вес - значение единицы отдельного разряда. Тогда, очевидно, все анаграммы будут иметь одинаковый вес.

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

В любом случае, задача сводится к построению метрики (оценке расстояния между словами), нечувствительной к порядку букв, но чувствительной к самим буквам и их количеству. Слова с нулевым расстоянием являются анаграммами.

@curtis65 · 16.04.2013, 23:06 **[ТС]**

gazlan, это все понятно,но сам код мне никак не понятен...как все описывать просто не понимаю

@gazlan · 16.04.2013, 23:56

Сам словарь - загруженный в память - у вас есть? Или, хотя бы, вообще словарь?
Что уже сделано - кроме публикации условия?
По обработке текста здесь чуть ли не половина топиков - вы искали по форуму?

Покажите код и ткните пальцем - где не работает?

@curtis65 · 20.04.2013, 21:31 **[ТС]**

gazlan, вот сам код.
у меня только переворачивает слова,мне нужно чтобы перебирал буквы

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
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
 
using namespace std;
 
 
 
int main()
{
    setlocale (LC_ALL,"rus");
   string base[] = {"мор", "туш", "шут", "ром", "хан", "хна",
                    "кот", "ток", "воз", "зов", "гам", "маг","полк","клоп"};
  
   size_t size = sizeof(base) / sizeof(*base);
 
   for (size_t i = 0; i < size-1; ++i)
   {
      string word = base[i];
      reverse(word.begin(), word.end());
 
      for (size_t j = i+1; j < size; ++j)
      {
         if (word == base[j])
         {
             cout<<"Anagramm"<<endl;
            cout << base[i] << "-" << base[j] << endl;
            break;
         }
      }
   }
 
   system("pause");
 
   return 0;
}

@gazlan · 20.04.2013, 23:06

Вы уверяли, что вам все понятно. Судя по коду - не все.

Реверсировать ничего не нужно. И переставлять ничего не нужно. От каждого слова нужно построить числовую характеристику ("вес"). И их сравнить.

Вот, начиная с 21 строки, все выбрасываете и делаете как написано в #2.

Пусть, например, ваш алфавит состоит из 5 букв: 'к', 'м','о','р', и 'т'. Тогда, (основание) > 5 - это 6. Присваиваем нашим буквам веса: 'к' - 1, 'м' - 6, 'о' - 36, 'р' - 216, 'т' - 1296

Вес слова "мор": 6 + 36 + 216 = 258
Вес слова "ром": 216 + 36 + 6 = 258
Вес слова "кот": 1 + 36 + 1296 = 1333
Вес слова "ток": 1296+ 36 + 1 = 1333

Веса "мор" и "ром" совпали - анаграмма. Веса "кот" и "ток" совпали - анаграмма. Слова разного размера не проверяете.

Если не учитывать регистр, букву 'ё', и ограничить максимальный размер слова 32 символами, то для русского алфавита 33 будет подходящим основанием.

@Ihor3 · 04.06.2013, 02:27

а если мне нужно с файла считывать и у файл записывать как это будет выглядеть?

@Nikita110001 · 25.01.2019, 18:06

Найти все анаграммы при условии, что файл большой (например, 1 ТБ), а памяти немного (приложение не должно "съесть" больше 1 ГБ).

@SomniPhobia · 25.01.2019, 19:10

curtis65, привет!

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
#include <iostream>
#include <windows.h>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    system("color 0A");
    setlocale(LC_ALL, "rus");
 
    vector<string> words;
    words.push_back("анх");
    words.push_back("мор");
    words.push_back("мро");
    words.push_back("туш");
    words.push_back("нора");
    words.push_back("шут");
    words.push_back("тор");
    words.push_back("ром");
    words.push_back("хан");
    words.push_back("нах");
    words.push_back("рано");
    words.push_back("рмо");
    words.push_back("омр");
    words.push_back("кум");
    
    vector<pair<size_t, size_t>> weights(words.size());
    size_t ind = 0u;
    for (const auto &word : words)
    {
        size_t sum = 0u;
        for (const auto &c : word)
        {
            sum += toupper(static_cast<unsigned char>(c));
        }
        weights[ind] = make_pair(ind, sum);
        ++ind;
    }
 
    auto predicate = []
    (
        pair<size_t, size_t> p1,
        pair<size_t, size_t> p2
    )
    {
        return p1.second > p2.second;
    };
    sort(weights.begin(), weights.end(), predicate);
    auto flag = false;
 
    for (size_t u = 1u; u < words.size(); ++u)
    {
        if (weights[u - 1].second == weights[u].second)
        {
            cout << words[weights[u - 1].first] << " ";
            flag = true;
        }
        else if(flag)
        {
            cout << words[weights[u - 1].first] << endl;
            flag = false;
        }
    }
    if (flag)
    {
        cout << words[(*weights.rbegin()).first] << endl;
        flag = false;
    }
    cout << endl;
 
    system("pause");
    return 0;
}

@Nikita110001 · 25.01.2019, 20:12

как написать такую программу как работает этот сервер только на C# только через процедуру ?
Слова Анграм будем брать из файла
https://wordhelp.ru/comb/анаграмма

Добавлено через 2 минуты
То есть что бы не я разгадывал слово а программа подбирала анаграмму к слову понимаете что я хочу реализовать на C# как это сделать по ка что не знаю

Добавлено через 33 секунды
То есть составить слова из букв

Добавлено через 37 секунд
https://wordparts.ru/anagramma/ как тут можно ли это реализовать помогите пожалуйста ?

Добавлено через 41 секунду
Сможете помочь в данной теме Написать программу "Анаграммы" ?

Добавлено через 51 минуту
Анаграмма - слово анаграмма происходит от греческих слов, смысл которых можно толковать как "Новая запись". Это способ перестановки букв, в результате которого получается новое слово или сочетание слов. Сейчас анаграммами называют просто перемешивание букв составляющих исходное слово, иногда перемешивание производится с сохранением слогов, таким образом облегачая поиск исходного слова. Довольно часто анаграммы используются для получения псевдонимов, беря за базу настоящее имя. К пример имя: Дима может трансформироваться в Амид или Идам, а фамилия Орлов в Ролов, Лоров. Анаграммы можно также использовать в качестве тренировки эрудиции, разгадывая при этом незнакомые или малознакомые слова.

Наш онлайн сервис (программа), по разгадыванию анаграмм, поможет быстро найти нужное решение. Одной из особенностей сервиса является возможность составления собственной анаграммы и просмотр значений слов, ведь многие слова наверняка окажутся незнакомыми. Слова можно вводить разделяя пробелом, тогда программа их обработает все. Если необходимо составить слова из заданного набора букв (или другого слова), достаточно выбрать необходимое действие и нажать enter либо кнопку "найти". Сервис будет отличным помощником, если потребуется помощь в игре "Словоед".

Если вам необходима помощь в игре виселица, то вы можете использовать функцию подбора по маске, заменяя пропущенные буквы с помощью симола '*' или символа '_', например для слова тетрадь маска может быть такой Т**Р*Д* и т.д. сервис выдаст подходящие для данной маски слова.

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

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

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

@curtis65 0 / 0 / 0 Регистрация: 14.04.2013 Сообщений: 12

	Задается словарь. Найти в нем все анаграммы 15.04.2013, 23:33. Показов 12283. Ответов 9 Метки нет (Все метки) задали задачу Задается словарь. Найти в нем все анаграммы (слова, составленные из одних и тех же букв). смысл понятен,но непонятно как проверять посимвольно, чтоб выдавал правильный результат! Помогите!! 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	16.04.2013, 04:20
	Поскольку для анаграммы порядок букв неважен, остаются только такие характеристики слова, как использованные буквы и их количество. Самый простой и быстрый вариант - это испортить словарь: отсортировать внутри каждого слова все буквы по алфавиту, а затем сами слова по по алфавиту. Остальное тривиально. Если словарь портить нельзя... Слова с разным количеством букв анаграммами быть не могут - проверяете только слова одинакового размера. Для каждого слова создаете массив счетчиков букв (33, если не различать регистр). Если для двух слов состояния счетчиков букв совпали - они являются анаграммой. Проходите в цикле по списку слов (словарю) и за квадратичное время находите все анаграммы. Если словарь предварительно отсортировать по размеру и по алфавиту, то будет быстрее :-) Как (эквивалентный) вариант, можно выбрать систему счисления с (основание) > (число букв) и (основание) > (максимальная длина слова) и присвоить каждой букве вес - значение единицы отдельного разряда. Тогда, очевидно, все анаграммы будут иметь одинаковый вес. На первом шаге алгоритма за линейное время взвешиваем все слова, на втором - за логарифмическое - сортируем, на третьем - распечатываем все последовательности одинакового веса. На большом словаре, разница в производительности должна быть значительной. В любом случае, задача сводится к построению метрики (оценке расстояния между словами), нечувствительной к порядку букв, но чувствительной к самим буквам и их количеству. Слова с нулевым расстоянием являются анаграммами. 0

@curtis65 0 / 0 / 0 Регистрация: 14.04.2013 Сообщений: 12
	16.04.2013, 23:06 [ТС]
	gazlan, это все понятно,но сам код мне никак не понятен...как все описывать просто не понимаю 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	16.04.2013, 23:56
	Сам словарь - загруженный в память - у вас есть? Или, хотя бы, вообще словарь? Что уже сделано - кроме публикации условия? По обработке текста здесь чуть ли не половина топиков - вы искали по форуму? Покажите код и ткните пальцем - где не работает? 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	20.04.2013, 23:06
	Вы уверяли, что вам все понятно. Судя по коду - не все. Реверсировать ничего не нужно. И переставлять ничего не нужно. От каждого слова нужно построить числовую характеристику ("вес"). И их сравнить. Вот, начиная с 21 строки, все выбрасываете и делаете как написано в #2. Пусть, например, ваш алфавит состоит из 5 букв: 'к', 'м','о','р', и 'т'. Тогда, (основание) > 5 - это 6. Присваиваем нашим буквам веса: 'к' - 1, 'м' - 6, 'о' - 36, 'р' - 216, 'т' - 1296 Вес слова "мор": 6 + 36 + 216 = 258 Вес слова "ром": 216 + 36 + 6 = 258 Вес слова "кот": 1 + 36 + 1296 = 1333 Вес слова "ток": 1296+ 36 + 1 = 1333 Веса "мор" и "ром" совпали - анаграмма. Веса "кот" и "ток" совпали - анаграмма. Слова разного размера не проверяете. Если не учитывать регистр, букву 'ё', и ограничить максимальный размер слова 32 символами, то для русского алфавита 33 будет подходящим основанием. 0

@Ihor3 3 / 3 / 1 Регистрация: 14.11.2012 Сообщений: 235
	04.06.2013, 02:27
	а если мне нужно с файла считывать и у файл записывать как это будет выглядеть? 0

@Nikita110001 20 / 19 / 4 Регистрация: 22.03.2018 Сообщений: 701
	25.01.2019, 18:06
	Найти все анаграммы при условии, что файл большой (например, 1 ТБ), а памяти немного (приложение не должно "съесть" больше 1 ГБ). 0

@Nikita110001 20 / 19 / 4 Регистрация: 22.03.2018 Сообщений: 701
	25.01.2019, 20:12
	как написать такую программу как работает этот сервер только на C# только через процедуру ? Слова Анграм будем брать из файла https://wordhelp.ru/comb/анаграмма Добавлено через 2 минуты То есть что бы не я разгадывал слово а программа подбирала анаграмму к слову понимаете что я хочу реализовать на C# как это сделать по ка что не знаю Добавлено через 33 секунды То есть составить слова из букв Добавлено через 37 секунд https://wordparts.ru/anagramma/ как тут можно ли это реализовать помогите пожалуйста ? Добавлено через 41 секунду Сможете помочь в данной теме Написать программу "Анаграммы" ? Добавлено через 51 минуту Анаграмма - слово анаграмма происходит от греческих слов, смысл которых можно толковать как "Новая запись". Это способ перестановки букв, в результате которого получается новое слово или сочетание слов. Сейчас анаграммами называют просто перемешивание букв составляющих исходное слово, иногда перемешивание производится с сохранением слогов, таким образом облегачая поиск исходного слова. Довольно часто анаграммы используются для получения псевдонимов, беря за базу настоящее имя. К пример имя: Дима может трансформироваться в Амид или Идам, а фамилия Орлов в Ролов, Лоров. Анаграммы можно также использовать в качестве тренировки эрудиции, разгадывая при этом незнакомые или малознакомые слова. Наш онлайн сервис (программа), по разгадыванию анаграмм, поможет быстро найти нужное решение. Одной из особенностей сервиса является возможность составления собственной анаграммы и просмотр значений слов, ведь многие слова наверняка окажутся незнакомыми. Слова можно вводить разделяя пробелом, тогда программа их обработает все. Если необходимо составить слова из заданного набора букв (или другого слова), достаточно выбрать необходимое действие и нажать enter либо кнопку "найти". Сервис будет отличным помощником, если потребуется помощь в игре "Словоед". Если вам необходима помощь в игре виселица, то вы можете использовать функцию подбора по маске, заменяя пропущенные буквы с помощью симола '' или символа '_', например для слова тетрадь маска может быть такой ТРД* и т.д. сервис выдаст подходящие для данной маски слова. В недавнем обновлении мы расширили словарь, теперь вы можете находить не только существительные, но и другие слова, такие как географические названия, фамилии, имена - используемые при разгадывании кроссвородов и сканвородов. Если вы разгадываете только анаграммы, то вам подойдет отдельная наша программа, предназначенная только для решения и составления анаграмм. Если же вам необходимо только составлять слова из длинных слов или букв, то так же есть отдельное приложение предназначенное для составления слов из букв. Отдельный сервис поиска слов по маске также доступен на нашем сайте. Дополнительно для разгадывания кроссвордов и сканвордов и вообще для поиска нужного слова, на сайте появился отличный помощник кросвордиста для поиска по описанию и маске слова одновременно. 0