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 thekth lexicographic permutation of the vectora.
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 