Next_permutation和效率

Question

从一个范围内的对象的可能随机排序开始是更有效的,使用next_permutation逐步执行所有更大的排列,然后逐步降低,再次使用原始排序,使用prev_permutation到达最后一个.

或者,在置换之前对范围进行排序,然后仅使用next_permutation来逐步完成所有这些操作？

Answer 1

next_permutation将逐步完成所有排列,而不仅仅是通过更大的排列.无需还原和使用prev_permutation,当然也不需要排序.

您只需要注意这样一个事实:一旦它"翻转"到字典上最低的排列,next_permutation就会返回false,因此您需要跟踪当前排列的数量,以便知道何时停止.

也就是说,无论起始范围如何,以下内容都将遍历范围的所有可能排列.

size_t const num_permutations = multinomial_coefficient(range);

for (size_t i = 0; i < num_permutations; ++i) {
    next_permutation(range.begin(), range.end());
    // use permutation.
}

该范围内不同元素数量multinomial_coefficient的多项系数在哪里？在所有元素都不同的简单情况下,这相当于N !,元素数量的阶乘.