next_permutation not by reference?

Question

I do not understand why inside the loop, the position of the values are changed. But outside do, while loop, all the values return to the original positions. Thus i need the //here code. I also tried a pointer array, but it showed the same behavior. Why so?

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int a[] = {0, 1, 2};
    do
    {
        for (int i = 0; i < 3; i++)
            cout << a[i];
        cout << endl;
    } while (next_permutation(a, a + 3));
    cout << endl;
    // here
    a[0] = 2;
    a[1] = 1;
    a[2] = 0;

    do
    {
        for (int i = 0; i < 3; i++)
            cout << a[i];
        cout << endl;
    } while (prev_permutation(a, a + 3));
    return 0;
}

{0, 1, 2} is lexicographically lowest, so if you continue looping based on std::next_permutation result, you will always end with this combination. — Yksisarvinen
– Yksisarvinen, Commented Jun 4, 2020 at 12:06

463035818_is_not_an_ai · Accepted Answer · 2020-06-04 12:11:22Z

1

Thats how next_permutation is defined. The last permutation (the one that returns false) is the one that puts the elements in sorted order.

I suppose there is another misunderstanding. Here:

do
{
    print_permutation();
} while (next_permutation(a, a + 3));

The last permutation you print inside the loop is that one before the one that makes next_permutation return false. Hence in the last iteration you are not printing the same permutation as outside of the loop. It is similar to:

bool increment(int& i) {
    ++i;
    return i<10;
}

int i = 0;
do {
   std::cout << i;
} while( increment(i) );

std::cout << i;

The last value printed inside the loop is 9, but the value of i after the loop is 10.

answered Jun 4, 2020 at 12:11

463035818_is_not_an_ai

129k11 gold badges116 silver badges240 bronze badges

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

Comments

ilim · Accepted Answer · 2020-06-04 12:21:16Z

Every time it is called, std::next_permutation generates an permutation P' of the given container a where the current permutation is, say, P. As long as the permutation P' it generates is greater than P, it returns true. However, in the case for P being the greatest (i.e., see below for an explanation of greatness) permutation of the elements in the given container a, for instance P=[2, 1, 0] the next permutation P' it generates is [0, 1, 2], which is not greater than P. In that case, it returns false and the loop terminates. But, due to the side effect of the process, once the function returns, the elements in the container are already placed in that smallest permutation possible. That is why you see those elements in their smallest permutation possible after the loop terminates.

The word greater may be a little confusing. Basically std::next_permutation uses whatever comparison operators are available to compare individual elements and ends up iterating over them in a way that lexicographically increases with each following permutation. So, for a vector of [0, 1, 2], it would iterate the following permutations in that order:

0, 1, 2
0, 2, 1
1, 0, 2
1, 2, 0
2, 0, 1
2, 1, 0

That is why, the function recognizes that [0,1,2] would not be a greater permutation after [2,1,0] and returns false.

Collectives™ on Stack Overflow

next_permutation not by reference?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related