实现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，3，它有6!/2!3！= 60排列。

Answer 2

在数学中，函数阶乘!n表示n个元素的排列数。

正如Berg和Greg所建议的，如果集合中有重复的元素，为了考虑它们，我们必须将阶乘除以每个不可区分的组(由相同元素组成的组)的排列数。

下面的实现计算范围内元素的排列数[第一，结束]。不需要对范围进行排序。

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