# Is there a function behaving the same as next_permutation does in C++?

I’m writing algorithms to solve a problem on LeetCode, and I need to find the next permutation of a vector. I wonder there is any function can help me.
Many thanks.

could use `permutations(a)` from `Combinatorics.jl`

You can use `Combinatorics.jl` as @jling said, namely:

• `nthperm(a, k)` : Compute the `k` th lexicographic permutation of the vector `a` .

However, the behavior is not the same as that of next_permutation.

``````julia> nthperm([3, 2, 1], 2)
3-element Vector{Int64}:
3
1
2
``````

which is supposed to be `[1, 2, 3]`

``````#include<algorithm>
#include <iostream>
using namespace std;

int main(){
int a[] = {3, 2, 1};
next_permutation(a, a + 3);
for (int i = 0; i < 3; ++i){
cout << a[i];
}
return 0;
}
``````
``````❯ g++ test.cpp

❯ ./a.out                                                                                   [127]
123
``````

That would do much more abundant calculation than just calculating the next permutation.

May be I’m missing something but, why do you say they are not the same?

``````julia> [nthperm([1, 2, 3],i) for i in 1:6]
6-element Vector{Vector{Int64}}:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
``````

and

``````#include<algorithm>
#include <iostream>
using namespace std;

int main(){
int a[] = {1, 2, 3};
do {
cout << a[0] << ' ' << a[1] << ' ' << a[2] << '\n';
} while (next_permutation(a, a + 3));
return 0;
}
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
``````

I guess they are just called differently, in C++ you have to go from one permutation to the next in order, but in Julia you can jump directly to any permutation.
Edit:
They are different in a way that C++ has no `next_permutation` of `{3, 2, 1}`, so it prints a sorted version of the original vector at the end. In Julia, it permutes by index, so it seems to be not `lexicographic` here.

So this is pretty confusing. And in Combinatorics.jl, `nthperm([1, 2, 2], 2)` will give `[1, 2, 2]`. So `nthperm(nthperm([1, 2, 2], 2), 2)` will stay at `[1, 2, 2]`, which is not what I need.

A “next” permutation only makes sense when you have a clear definition of what “next” is supposed to mean. You seem to want it to mean “the next permutation of a given vector in a lexicographic ordering of all permutations of that vector”, which I don’t think is part of the Combinatorics.jl API by itself since that package deals with mathematical permutations in the form of vectors (i.e., lists of indices describing a permutation).

If you expected `[2,1,2]` instead, you’ve hit an off-by-one error in your mental model, since julia uses 1-based indexing. The first and second permutation is the same and you didn’t specify whether you need unique permutations or not:

``````julia> permutations([1,2,2]) |> collect
6-element Vector{Vector{Int64}}:
[1, 2, 2]
[1, 2, 2]
[2, 1, 2]
[2, 2, 1]
[2, 1, 2]
[2, 2, 1]
``````

If that’s not what you expected, what do you want the result to be?

1 Like

they are the same, in C++ you have to sort the array first, that’s how you can guarantee you will go through all permutations by calling next permutations in a loop.

in Julia you will be doing essentially the same thing. have you tried it? is Julia significantly slower or something that made you say that?

Sure, and it is what `next_permutation` does in C++.

You can check the C++ code

``````#include<algorithm>
#include <iostream>
using namespace std;

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

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

And it will give

``````212
221
122
``````

I don’t want to get all the n! permutations, but just the next permutation in lexicographic ordering, like `next_perm([3, 2, 1]) -> [1, 2, 3]`

The C++ version seems to only give unique permutations.

Here’s a function that achieves the same thing, translated from C++ algorithm.h (which is GPL licensed, but I doubt people would sue me for making a julia port available. Nevertheless, don’t put it in a MIT licensed package if you’re careful about this stuff. Or do, I’m not a lawyer ): Here be GPL dragons.

This does require the input to be indexable, but that’s not too much of a problem since general iterators in julia may not even have a defined order of elements you could swap, like the C++ Iter thing seems to guarantee. Too much pointer fiddling…

Now for those who don’t want to read GPL code, here’s a verbatim explanation so some brave soul can reimplement it and make it MIT compatible:

The algorithm is fairly simple, but still achieves O(n) (with constant factor 2 in the worst case that the list is already in reverse sorted order). We basically check trivial cases first (e.g. is the list empty or only has one element?). After that we can just go through the list in reverse, looking for an element that’s smaller than the one after it (i.e. with a higher index). So e.g. in `[1,2,4,3]` we’d do our first real work once we hit the element `2` (index 2). Our last element was a `4` (index 3). Since we hit a smaller element, we know that some element between index 2 and the last index (4 in this case) has to be bigger than 2, but it may still be smaller than the last element we looked at. So we go looking for the first element between our the last index and our current index that’s still larger than our current element. Once we find it, we just swap the two elements. Finally, we have to reverse all elements between our last element (index 3) and the last index, since we have put the smallest known element at the end of our list, even though we want to have it at the front of the tail part of our list.

If the list is sorted in reverse order, we just reverse it in place instead (this is where the factor 2 in the worst case comes from, since we have to run through the list once to check if it is sorted in reverse order, and run through again to reverse it).

3 Likes
``````function next_perm!(itr)::Bool
(isempty(itr) || length(itr) == 1) && return false

i = findlast(idx -> itr[idx + 1] > itr[idx], 1:lastindex(itr) - 1)
isnothing(i) && (reverse!(itr); return false)

j = findlast(idx -> itr[idx] > itr[i], i+1:lastindex(itr)) + i
itr[i], itr[j] = itr[j], itr[i]
reverse!(itr, i + 1)
return true
end
``````

That seems nice! If you wrote it without looking at the GPL’d code from the gist, you’ve just succeeded in reimplementing an algorithm Otherwise, welp, it’s GPL’d and it would have been better to not put it into discourse directly in order to prevent people from accidentally reading GPL’d code