Лучший способ реализовать count_permutations?

Question

Мне нужна функция count_permutations (), которая возвращает количество перестановок заданного диапазона. Предполагая, что диапазон может быть изменен и начинается с первой перестановки, Я мог бы наивно реализовать это как повторяющиеся вызовы next_permutation (), как показано ниже:

template<class Ret, class Iter>
Ret count_permutations(Iter first, Iter last)
{
    Ret ret = 0;
    do {
        ++ret;
    } while (next_permutation(first, last));
    return ret;
}

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

Answer 1

Число перестановок для диапазона, в котором все элементы уникальны, равно n! где n - длина диапазона.

Если имеются повторяющиеся элементы, вы можете использовать n! / (N_0!) ... (n_m!), Где n_0 ... n_m - длины дублированных диапазонов.

Так, например, [1,2,3] имеет 3! = 6 перестановок, в то время как [1,2,2] имеет 3! / 2! = 3 перестановки.

РЕДАКТИРОВАТЬ: Лучшим примером является [1,2,2,3,3,3], который имеет 6! / 2! 3! = 60 перестановок.

Answer 2

В математике функция factorial! N представляет количество перестановок n элементов.

Как могли предположить Берг и Грег, если в наборе присутствуют повторяющиеся элементы, мы должны разделить факториал на число перестановок каждой неотличимой группы (групп, состоящих из одинаковых элементов).

Следующая реализация подсчитывает количество перестановок элементов в диапазоне [first, end). Диапазон не требуется сортировать.

// generic factorial implementation...

int factorial(int number) {
    int temp;
    if(number <= 1) return 1;
    temp = number * factorial(number - 1);
    return temp;
}

template<class Ret, class Iter>
Ret count_permutations(Iter first, Iter end)
{
    std::map<typename Iter::value_type, int> counter;
    Iter it = first;
    for( ; it != end; ++it) {
        counter[*it]++;
    }

    int n = 0;
    typename std::map<typename Iter::value_type, int>::iterator mi = counter.begin();
    for(; mi != counter.end() ; mi++)
        if ( mi->second > 1 )
            n += factorial(mi->second);

   return factorial(std::distance(first,end))/n;
}