Next Permutation on Subsegment

Revision en18, by Guslix, 2021-08-21 14:15:26

To get the next permutation of array of its subsegment there is a simple and very old Narayana's algorithm. This algorithm invented by Indian mathematician Pandit Narayana more than 600 years ago.

Given array $$$a$$$. How to go to its next permutation?

  1. Find the longest non-increasing suffix of the array (LNIS). If whole array is non-increasing, permutations are exhausted.

  2. Let LNIS be a suffix $$$k$$$, where $$$k$$$ is position where it begins. Swap previous element, $$$a_{k-1}$$$ and the next largest number (NLN) that exists in suffix $$$k$$$.

  3. Reverse suffix $$$k$$$.

Time complexity: $$$O(n)$$$ in the worst case. But on average length LNIS is about 3 elements, so iteration over all permutations is doing for $$$O(n!)$$$, thus $$$O(1)$$$ for one permutation.

Although suddenly there is such a problem. Given an array of 100500 elements and 100500 queries to get next or previous permutation. If the array is sorted and first query is prev permutation on whole array, second query is next permutation on whole array, and further this loop is repeating; you must to walk over all array, answer each query for $$$O(n)$$$.

This algorithm can be implemented for $$$O(\log n)$$$ on a treap. Reversal is known, and swapping is just a combination of split and merge operations. Also we need to find LNIS and NLN. LNIS is sorted by definition, so we can apply binary search in order to find NLN of $$$a_{k-1}$$$.

Position $$$k$$$ of LNIS is found a recursive algorithm too. Let we in subtree $$$t$$$ now. First, find LNIS of right subtree of $$$t$$$. If the right subtree is not sorted in non-increasing order, we don't heed visit left subtree of $$$t$$$.

Else we should to compare value of root of $$$t$$$ with the first element of right subtree and the last element of left subtree. If still keeps a non-increasing order, continue the search in left subtree. To avoid additional costs, we need to maintain first and last elements and non-increasing order flag for each subtree and recalc it after each operation.

To get the previous permutation there's similar algorithm. Here is non-decreasing order instead of non-increasing one and next smallest element instead next largest one.

The Code

Time complexity: $$$O(\log n)$$$

Struct node
Lazy propagation of reverse
Recalc of size and other node parameters
Split
Merge
Build a treap from array
Find k, the position of start LNIS
Find the position of NLN
void next_p(int L, int R, treap t=root){
    treap l, r, swap1, swap2, between;
    split(t, t, r, R+1, 0);
    int k = find_k(t, R)+1; //find LNIS
    split(t, l, t, max(L,k), 0); //separate LNIS
    t->reversed ^= 1;
    if(k>L) { //if the subsegment isn't in non-increasing order
        split(l, l, swap1, k-1, 0); //separate a_(k-1)
        int nln = find_nln(t, swap1->val, k);
        split(t, between, t, nln, k); split(t, swap2, t, nln+1, nln); //separate NLN
        merge(t, swap1, t); merge(t, between, t); merge(t, swap2, t);
    }
    merge(t, l, t); merge(t, t, r);
}
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)