Same permutations in two arrays using next_permutation() stl in c++

Question

Is there is a easy way to make next_permutation to perform same set of swaps two different arrays of same size for example if i have two arrays a[]={1,2,3,4,5} and b[]={12,23,21,2,3} if after permution 1 in array a goes to 3rd position then 12 in array b should also go to 3rd position.

Answer 1

You can make an auxiliary index set:

int a[] = { 1, 2, 3, 4, 5 };
int b[] = { 12, 23, 21, 2, 3 };

std::size_t indices[] = { 0, 1, 2, 3, 4 };

Now perform the permutations on indices, and then use a[indices[i]] and b[indices[i]].

Answer 2

Keep in mind that std::next_permutation doesn't keep any state (it would go against the concept of stl algorithms). So how does it generate the next permutation? It does it by the order of the elements. That's why there's a version that accepts a comparison operator

If you give it a sorted array of size N, then next_permutation can be called N! times. Otherwise, you have less permutations before the algorithm returns false.

To answer your question, if the arrays have the same order in terms of the "auxiliary index set" as suggested above, then the same elements would be swapped.

Example:

int a[] = { 1, 2, 4, 3 };
int b[] = { 11, 12, 14, 13 };

These will be permuted the same, because sort will produce the same index ordering.