C++ next_permutation без листинга в обратном порядке

Question

Есть ли способ распечатать все перестановки, опуская перестановки, которые уже встречаются в обратном порядке, используя next_permutation в C++. Например, после печати {1, 2, 3, 4} он не должен печатать {4, 3, 2, 1}.

Answer 1

Пока первый элемент перестановки лексикографически меньше последнего элемента, вы не получите никаких перестановок, которые будут дублировать при обратном:

std::vector<int> v {1, 2, 3, 4}; 

do { 
    if (v.front() < v.back()) { // first less than last 
     std::copy(v.begin(), v.end(), 
        std::ostream_iterator<int>(std::cout, " ")); 
     cout << '\n'; 
    } 
} 
while (std::next_permutation(v.begin(), v.end())); 

Answer 2

При генерации перестановок в порядке возрастания последовательности вы можете просто опустить любую перестановку, последний элемент которой меньше ее первого элемента (его обратный уже указан).

Поскольку число перестановок п элементов является п!, Избавляя половина не влияет на производительность большой-O.