Лучший способ реализовать 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; 
} 

Есть ли более быстрый способ, который Безразлично» t требует итерации через все перестановки, чтобы найти ответ? Он все же может предположить, что вход может быть изменен и начинается с первой перестановки, но, очевидно, если это возможно реализовать без этих предположений, было бы здорово.

Answer 1

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

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

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

EDIT: Лучшим примером является [1,2,2,3,3,3], который имеет 6!/2! 3! = 60 перестановок.

Answer 2

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

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

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

// 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; 
}