C++ <algorithm> permutation

Question

Why is this code note working (the code compiles and run fine, but is not actually showing the permutations):

int main(int argc, char *argv[])
{
    long number;
    vector<long> interval;
    vector<long>::const_iterator it;

    cout << "Enter number: ";
    cin >> number;

    while(number-->0){
        interval.push_back(number);
    }

    do{
        for(it = interval.begin(); it < interval.end(); ++it){
            cout << *it << " ";
        }
        cout << endl;
    } while(next_permutation(interval.begin(), interval.end()));

    return (0);
}

But after changing this line:

while(next_permutation(interval.begin(), interval.end()));

with:

while(prev_permutation(interval.begin(), interval.end()));

Isn't permutation changing the elements in the vector by acting on positions ?

PS: I've edited the code now.

Answer 1

Permutations are lexicographically ordered, that's what next_permutation and prev_permutation algorithms traverse. See here.

Here you enter the "biggest" permutation, so there's no next one in order.

Answer 2

I don't think next_permutation can work on positions (where will it store that info?). You need to be able to compare elements for next_permutation to work, and that is what it uses to generate the lexicographically next permutation.

Try inserting the numbers in the reverse order and see if that works.

Answer 3

Isn't permutation changing the elements in the vector by acting on positions ?

No. next_permutation uses the ordering of the elements to determine the next permutation.

For example, if A < B < C, then the next_permutation of [A,B,C] (012) would be [A,C,B] (021). However, if A < C < B, then the next_permutation of [A,B,C] (021) would be [C,A,B] (102).

Since your vector was initially in decreasing order, it would have been the last permutation.

You could use the std::greater ordering to reverse the comparison direction.

} while(next_permutation(interval.begin(), interval.end(), greater<long>()));
//                                                         ^^^^^^^^^^^^^^^