Is it possible to perform this for $$$O(log N)$$$ ?
An algorithm for obtaining the next permutation of the set of numbers was invented by Indian mathematician Pandit Narayana more than 600 years ago. Given array $$$a$$$. The way the next permutation is found with Narayana's algorithm: 1. Find the longest non-decreasing suffix. Let in starts in position $$$k$$$. If $$$k=0$$$, permutations are exhausted. 2. Swap $$$a_{k-1}$$$ and the next largest number that exists in suffix $$$k$$$. 3. Reverse suffix $$$k$$$. On a subsegment of the array the next permutation can be found in the same way.
Time complexity: $$$O(N)$$$, because in worst case suffix can be of length $$$n-1$$$. But there is a way to reverse a subsegment for $$$O(log N)$$$ using a treap. So the problem to obtain the next permutation for $$$O(log N)$$$ can be transformed to subsegment reversing.
First, reverse the longest non-decreasing suffix (NDS). Then it get sorted, so we can apply binary search in order to find the next largest number of $$$a_{k-1}$$$. Swapping is just a combination of split and merge operations.
The Code
void next_p(int l, int r, treap t=root){
treap lt,rt, swap1,swap2, t2;
split(t,t,rt,r+1);
int tail = tail(t);
if(tail==l){
t->reversed^=1; //just reverse it
merge(t,t,rt); return;
}
l=tail; //elements to the left aren't changed
split(t,lt,t,l-1); split(t,swap1,t,l); //separate p_(n-k)
t->reversed^=1; //it's easier to reverse tail k before finding p_next
int p_next = upper_b(l,r,t); //find p_next by binary search
split(t,t2,t,p_next); split(t,swap2,t,p_next+1); //separate p_next
merge(t,swap1,t); merge(t,t2,t); merge(t,swap2,t); //unite tail k+1
merge(t,lt,t); merge(t,t,rt); //unite all
}