实现计数置换的更好方法?

在所有元素都是唯一的范围内,排列的数目是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个排列。

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

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

以下实现统计范围[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;
}