Формула подсчета перестановок

@Fixer_84 · Регистрация: 30.04.2016

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

Здравствуйте, уважаемые пользователи! На этот раз, обращаюсь к гуру комбинаторики, за простым советом. Есть вот такая несложная задача:

Анаграммы

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

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

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

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

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

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

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

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

Решение этой задачи легко сводится к перебору с использованием функции next_permutation(), однако, программа в последнем тесте не проходит по времени. Помню, как на практике, решали задачки по теории вероятностей с использованием формул C(n, k) и A(n, k). Если я ничего не перепутал, то зная входные данные (типа ABCDDD - ответ 120), можно получить формулу для расчета всевозможных комбинаций, но как эта формула выглядит - не помню

Например, для ABCDDD можно подсчитать длину строки (=6) и число различных символов в ней (=4) и оперируя этими цифрами получить ответ (используя специальную формулу, которую я и хочу использовать для решения задачи. Буду благодарен всем, кто сможет помочь.

Мое решение:

C++

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    string s;
    int N;
    getline(cin, s);
    sort(s.begin(), s.end());
    N = 0;
    do
    {
        N++;
    } while (next_permutation(s.begin(), s.end()));
    cout << N << endl;
    system("pause");
    return 0;
}

Croessmah · 13.08.2017, 18:45

n! / k!, где n - количество знаков, а k - количество повторяющихся элементов?

@Fixer_84 · 13.08.2017, 19:25 **[ТС]**

Croessmah, да, похоже вы правы

Сейчас сделаю решение и сюда выложу. Спасибо огромное!

Добавлено через 14 минут
Croessmah, а как будет для ABCCDDFF? (8! / 6!) = 40320 / 720 = 56, а должно быть 5040.

Добавлено через 19 минут
Croessmah, можете не отвечать, я понял. Тут для каждого набора символов нужно k! считать

То есть, для ABCCDDFF будет: 8! / (2! * 2! * 2!), где 2 - количество вхождений (не)уникального символа

Croessmah · 13.08.2017, 19:28

Сообщение от Fixer_84

можете не отвечать

Ну ок.

Сообщение от Fixer_84

Сейчас сделаю решение и сюда выложу.

Хоть сработало?

@Fixer_84 · 13.08.2017, 19:40 **[ТС]**

Croessmah, да, вот решение, но теперь в последнем тесте - неправильный ответ. Можете помочь? Все, вроде, правильно и по времени теперь - идеально

Решение:

C++

#include <bits/stdc++.h>
 
using namespace std;
 
int Fact(int N)
{
    if (N == 1)
        return 1;
    else
        return N * Fact(N - 1);
}
 
int main()
{
    string str;
    int x, y, p;
    getline(cin, str);
    sort(str.begin(), str.end());
    x = y = 0;
    p = 1;
    for (int i = y; str[i]; i++)
    {
        if (str[i] == str[i+1])
        {
            x++;
        }
        else
        {
            y = x;
            x++;
            if (x > 1)
                p *= Fact(x);
            x = 0;
        }
    }
    cout << Fact(str.size()) / p << endl;
    system("pause");
    return 0;
}

Добавлено через 3 минуты
Croessmah, все, сдал

Не тот тип данных просто использовал

Спасибо вам!

Рабочее решение:

C++

#include <bits/stdc++.h>
 
using namespace std;
 
long long Fact(int N)
{
    if (N == 1)
        return 1;
    else
        return N * Fact(N - 1);
}
 
int main()
{
    string str;
    long long x, y, p;
    getline(cin, str);
    sort(str.begin(), str.end());
    x = y = 0;
    p = 1;
    for (int i = y; str[i]; i++)
    {
        if (str[i] == str[i+1])
        {
            x++;
        }
        else
        {
            y = x;
            x++;
            p *= Fact(x);
            x = 0;
        }
    }
    cout << Fact(str.size()) / p << endl;
    system("pause");
    return 0;
}

Croessmah · 13.08.2017, 20:00

Сообщение от Fixer_84

и по времени теперь - идеально

Можно факториал "затабличить".

Croessmah Неэпический 18100 / 10686 / 2061 Регистрация: 27.09.2012 Сообщений: 26,899 Записей в блоге: 1
	13.08.2017, 18:45	2
	n! / k!, где n - количество знаков, а k - количество повторяющихся элементов? 1

@Fixer_84 1505 / 968 / 812 Регистрация: 30.04.2016 Сообщений: 3,334
	13.08.2017, 19:25 [ТС]	3
	Croessmah, да, похоже вы правы Сейчас сделаю решение и сюда выложу. Спасибо огромное! Добавлено через 14 минут Croessmah, а как будет для ABCCDDFF? (8! / 6!) = 40320 / 720 = 56, а должно быть 5040. Добавлено через 19 минут Croessmah, можете не отвечать, я понял. Тут для каждого набора символов нужно k! считать То есть, для ABCCDDFF будет: 8! / (2! * 2! * 2!), где 2 - количество вхождений (не)уникального символа 1

Croessmah Неэпический 18100 / 10686 / 2061 Регистрация: 27.09.2012 Сообщений: 26,899 Записей в блоге: 1
	13.08.2017, 19:28	4
	Сообщение от Fixer_84 можете не отвечать Ну ок. Сообщение от Fixer_84 Сейчас сделаю решение и сюда выложу. Хоть сработало? 0

Croessmah Неэпический 18100 / 10686 / 2061 Регистрация: 27.09.2012 Сообщений: 26,899 Записей в блоге: 1
	13.08.2017, 20:00	6
	Сообщение от Fixer_84 и по времени теперь - идеально Можно факториал "затабличить". 0

Опции темы