e-olymp 390. Анаграммы

Задача

Анаграммой слова называется любая перестановка всех букв слова. Например, из слова SOLO можно получить 12 анаграмм: SOLO, LOSO, OSLO, OLSO, OSOL, OLOS, SLOO, LSOO, OOLS, OOSL, LOOS, SOOL.

Напишите программу, которая выводит количество различных анаграмм, которые могут получиться из этого слова.

Входные данные

Слово, количество букв в котором не превышает 14.

Выходные данные

Количество различных анаграмм.

Тесты

Ввод Вывод
1 SOLO 12
2 ANAGRAM 840
3 PERMUTATION 19958400
4 AAAAA 1
5 AABBBCCC 560

Код (string)

Код (c-string)

Решение

Данная задача решается с помощью единой формулы \begin{equation} N_s =\frac {length!}{p_1! × p_2! × \ldots\ × p_n!}\end{equation} где $ length$ — длина строки, а $p_i$ — количество повторений одной буквы $(i = 1, 2, \ldots\ , n$, $ n$ — количество различных букв). Буквы, повторяющиеся один раз, можем опустить, так как их факториал даст единицу, что никак не повлияет на результат.
Длину строки найдем с помощью метода size()(или strlen()), а количество повторений для удобства будем подсчитывать в контейнере map.

Ссылки

Задача 390 на e-olymp

Код на Ideone (string)

Код на Ideone (c-string)

Related Images:

4 thoughts on “e-olymp 390. Анаграммы

  1. Зачем Вы много раз вычисляете факториалы, да еще и рекурсивно? Можно же один раз посчитать динамикой.
    m[s[i]] = (m[s[i]] ? ++m[s[i]] : 1); — не имеет смысла. Это ровно то же самое, что ++m[s[i]]

    • Вы абсолютно правы. Спасибо за замечание

Добавить комментарий