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.

you posted twice the same line (changing this line with example) and what is prev_permutation? — RvdK
– RvdK, Commented Jun 29, 2010 at 14:57
I've just tested the source you posted (@JS Bangs: prev_permutation() is part of the STL) and everything is working in my opinion. Entering "3" lists all possible 6 combinations and so on. Can you please describe exactly what is not working? Please post your output for example. — tux21b
– tux21b, Commented Jun 29, 2010 at 15:11

Nikolai Fetissov · Accepted Answer · 2013-04-26 19:21:22Z

7

Permutations are lexicographically ordered, that's what std::next_permutation and std::prev_permutation algorithms traverse.

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

edited Apr 26, 2013 at 19:21

user283145

answered Jun 29, 2010 at 15:09

Nikolai Fetissov

84.6k13 gold badges118 silver badges175 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andrei Ciobanu Over a year ago

I understand now. So if I want to generate all the permutations I will need to have all the numbers sorted. Thanks!

rturrado Over a year ago

Exactly: sorted, and then use next_permutation. Or, reverse sorted, and then use prev_permutation.

Aryabhatta Over a year ago

@Andrie: Or just run both prev and next without the need to sort.

kennytm · Accepted Answer · 2010-06-29 15:15:53Z

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

answered Jun 29, 2010 at 15:15

kennytm

526k110 gold badges1.1k silver badges1k bronze badges

Comments

Aryabhatta · Accepted Answer · 2010-06-29 15:10:09Z

1

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.

answered Jun 29, 2010 at 15:10

Aryabhatta

Collectives™ on Stack Overflow

C++ <algorithm> permutation

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related