Next Permutation on Subsegment

Revision en6, by Guslix, 2021-08-19 20:19:06

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-increasing suffix (LNIS). Let in starts in position $$$k$$$. If $$$k=0$$$, permutations are exhausted. 2. Swap $$$a_{k-1}$$$ and the next largest number (NLN) 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 LNIS. Then it get sorted, so we can apply binary search in order to find NLN of $$$a_{k-1}$$$. Swapping is just a combination of split and merge operations.

But to find LNIS is more difficult. Let in each subtree maintain if the elements in this tree are non-increasing. Then recursion on the treap selects at most one subtree each step and find LNIS for $$$O(log N)$$$.

How to maintain this flag? Elements of a tree are non-increasing if and only if both subtrees are with non-increasing elements and last element of left subtree $$$\geq$$$ value of tree's root $$$\geq$$$ first element of right subtree. Empty subtrees don't affect the non-increasing order. Since we need to reverse subsegments, we should to maintain also a flag of non-decreasing order. These two flags are swapping while reversing.

The Code

Struct node
Recalc of size and other node parameters
Lazy propagation of reverse
Split
Merge
Build a treap from array
Find NDS
Find the next largest number
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
}
Tags next permutation, narayana, treap, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English Guslix 2021-08-21 14:15:26 45
en17 English Guslix 2021-08-20 20:00:01 51
en16 English Guslix 2021-08-20 19:58:14 53
en15 English Guslix 2021-08-20 19:51:12 1 Tiny change: '$O(\log n).$\n\n\n\n<' -> '$O(\log n)$\n\n\n\n<'
en14 English Guslix 2021-08-20 19:31:34 51 (published)
en13 English Guslix 2021-08-20 18:35:11 422
en12 English Guslix 2021-08-20 18:18:48 1405
en11 English Guslix 2021-08-20 15:34:52 1142
en10 English Guslix 2021-08-20 09:41:35 450
en9 English Guslix 2021-08-19 23:59:09 698
en8 English Guslix 2021-08-19 20:59:20 129
en7 English Guslix 2021-08-19 20:20:06 5
en6 English Guslix 2021-08-19 20:19:06 15
en5 English Guslix 2021-08-19 20:15:03 548
en4 English Guslix 2021-08-19 19:55:57 3193
en3 English Guslix 2021-08-19 19:40:49 670
en2 English Guslix 2021-08-19 19:01:53 402
en1 English Guslix 2021-08-19 10:54:29 1255 Initial revision (saved to drafts)