в std :: next_permutation отсутствует одна запись

Question

В следующей программе отсутствует одна запись перестановки.

#include <iostream>
#include <vector>
#include <algorithm>

int main ( int argc, char **argv) {
    std::vector<int> temp;
    temp.push_back(10);
    temp.push_back(2);
    temp.push_back(4);
    temp.push_back(4);

    do {
        std::copy(temp.begin(),temp.end(),std::ostream_iterator<int>(std::cout," "));
        std::cout << std::endl;
    }while ( std::next_permutation (temp.begin(), temp.end()));
}

Ниже приводится вывод программы

10 2 4 4
10 4 2 4
10 4 4 2

почему отсутствует одна запись, которая

2 4 4 10

Answer 1

Это потому, что эта перестановка является первым порядком для списка номеров, которые у вас есть. Вам нужно будет отсортировать исходный массив, тогда эта перестановка будет указана как самая первая.

std::vector<int> temp;
temp.push_back(10);
temp.push_back(2);
temp.push_back(4);
temp.push_back(4);
std::sort(temp.begin(),temp.end() );

В качестве альтернативы, вы можете просто толкать элементы в отсортированном порядке, но для практических целей вы всегда должны сортировать, если хотите генерировать все возможные перестановки.

Answer 2

На самом деле отсутствует несколько других допустимых перестановок: 2 10 4 4 и 2 4 10 4, и, например, 4 4 10 2.

Относительно того, почему они отсутствуют: в документации сказано:1006 *

Возвращаемое значение true, если функция может переставить объект как лексикографически большая перестановка.В противном случае функция возвращает false, чтобы указать, что расположение не больше предыдущего, но минимально возможное (отсортировано по возрастанию).

Таким образом, цикл while заканчивается после 10 4 4 2,потому что это лексикографически самая большая перестановка (та, которая «самая большая», когда вы сравниваете их слева направо, т.е. та, что в порядке убывания).После распечатки этого next_permutation не может перейти к «следующей» перестановке и переходит к «начальной» перестановке 2 4 4 10;но это не печатается, потому что функция также вернула false.