C++ next_permutation without listing in reverse order

Question

Is there any way to print all permutations omitting the permutations which already occur in reverse order by using next_permutation in C++. For example, after it printed {1, 2, 3, 4}, it should not print {4, 3, 2, 1}.

I am not sure I understand your issue. `1,2,3,4` is the first lexicographical permutation, if you use `next_permutation` it will print `1,2,4,3`, not `4,3,2,1`. Perhaps you're asking for [combinations](http://marcodiiga.github.io/permutations-and-combinations/) ? — Marco A., Sep 06 '15 at 09:06
Although for Python, the answers on [this question](http://stackoverflow.com/q/960557/2675154) provide some nice explanations. — honk, Sep 06 '15 at 09:59

score 2 · Answer 1 · answered Sep 06 '15 at 09:34

As long as the first element in a permutation is lexicographically less than the last element, you will not get any permutations that would be duplicate when reversed:

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()));

score 0 · Answer 2 · answered Sep 06 '15 at 09:38

When you generate the permutations in increasing sequence order you can simply omit any permutation whose last item is less than its first item (its reverse has already been listed).

Since the number of permutation of n items is n!, eliminating half does not impact on the big-O performance.

C++ next_permutation without listing in reverse order

2 Answers2