Следующая_перестановка и эффективность

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 !, факториал числа элементов.

Answer 2

Чтобы получить все перестановки, начните с отсортированного диапазона, затем

do
{
  // something
} while(next_permutation(range.begin(), range.end());

Останавливается, когда диапазон снова сортируется.Процесс O (n!).

Когда вы начнете с рандомизированного диапазона, вы пропустите некоторые перестановки.

Answer 3

Нет никакой разницы, алгоритм не использует предыдущие результаты, поэтому нет необходимости предварительно сортировать.