CODEWITHSUNDEEP
c++algorithmsortingpermutationprobability
Josh
Josh

Reputation: 3311

Prev_permutation vs Next_permutation difficulty

I was trying out a sample program to grasp the difference between prev and next permutation. However, my program doesn't seem to work properly. I start the program by asking the number of elements in the array and I build the array with a simple for loop 

for(i = 0; i < x; i++)
        ptr[i] = i;

cout << "Possible permuations using prev_permutation: " << endl;
    do{
        for(i = 0; i < x; i++)
            cout << ptr[i] << " ";
        cout << endl;
    } while(prev_permutation(ptr, ptr+x));

cout << "Possible permuations using next_permutation: " << endl;
do{
    for(i = 0; i < x; i++)
        cout << ptr[i] << " ";
    cout << endl;
} while(next_permutation(ptr, ptr+x));

When I run the code with a sample of 3 elements, (0, 1, 2). The prev_permutation gives me (0, 1, 2 and thats it). Then next_permutation gives me (2, 1, 0). However, when I comment the code for the prev_permutation part, I get a proper 6 different permutations of the set (0, 1, 2) when only next_permutation is running. I can't seem to understand what is going on.

Upvotes: 4

Views: 1239

Answers (2)

6502
6502

Reputation: 114549

prev_permutation and next_permutation generate all permutations in lexicographical ("alphabetical") order and they return false once the cycle has been completed (i.e. if after calling prev_permutation on the first permutation or after calling next_permutation on the last one).

What happens is that you prepare the array with the first permutation in lexicographical order, then you call prev_permutation. This is however the first, so prev_permutation sets the array to the last permutation and the returns false, so you exit the loop.

Now you enter the next_permutation loop, but the current content of the array is the last permutation in lexicographical order, so next_permutation will set the first one and will return false.

If you remove the prev_permutation part however the loop for next_permutation will start from the first and so it will generate correctly all 6 permutations before returning false.

You can visualize the effect considering all permutations listed in order and with the current configuration as a pointer in this list:

0-1-2 << you start here
0-2-1
1-0-2
1-2-0
2-0-1
2-1-0

when calling next_permutation you are moving down, when calling prev_permutation you are moving up. When going outside the list both function will move the pointer to the other end and will return false to inform you of this fact.

If you start with prev you move to 2-1-0 and function returns false, then you call next and the function move to 0-1-2 and returns false again.

Using for example instead of 0, 1 and 2 the permutations of two zeros and three ones the lexicographical ordering is:

0-0-1-1-1
0-1-0-1-1
0-1-1-0-1
0-1-1-1-0
1-0-0-1-1
1-0-1-0-1
1-0-1-1-0
1-1-0-0-1
1-1-0-1-0
1-1-1-0-0

So to enumerate all of them you need to start from 0-0-1-1-1 and use next_permutation or you need to start from 1-1-1-0-0 and use prev_permutation.

In this case calling next_permutation on the last one 1-1-1-0-0 will change to the first 0-0-1-1-1 and will return false; in a similar way calling prev_permutation on 0-0-1-1-1 will change to 1-1-1-0-0 and will return false because of the flip.

Upvotes: 8

Drew Dormann
Drew Dormann

Reputation: 63838

All the permutations considered by both prev_permutation and next_permutation have a well-defined lexicographical order. The array you provided to them has some position in that order.

That's why neither function is guaranteed to provide all permutations.

If you provide the first possible permutation to prev_permutation, which you did, there will be no permutations before it. Likewise, if your array were defined as (2, 1, 0), next_permutation would not provide any new permutations.

If you need all the permutations of some collection, you would want to sort the collection first and then use next_permutation.

Upvotes: 3

Related Questions