c++ - 实现 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 个排列。