更好的方法来实现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个排列.