Next Permutation on Subsegment

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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?

Find the longest non-increasing suffix of the array (LNIS). If whole array is non-increasing, permutations are exhausted.
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$$$.
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

struct node {
    int val, heap_val, size; //size of this tree
    node *l, *r; //left and right subtrees
    bool reversed, non_incr, non_decr;
    int first_elem, last_elem;
    node(int Val=0) : val(Val), size(1), l(0), r(0), reversed(0) {
        heap_val = rand() * (1<<15) + rand(); //now heap_val to 2^30
        non_incr = non_decr = 1;
        first_elem = last_elem = Val;
    }
};
typedef node* treap;
treap root;

Lazy propagation of reverse

void lazy_pr(treap t){
    if(!t || !t->reversed) return; //if the tree is nullptr or is already reversed even number of times
    t->reversed=0;
    swap(t->l, t->r), swap(t->non_incr, t->non_decr), swap(t->first_elem, t->last_elem);
    if(t->l) t->l->reversed ^= 1; if(t->r) t->r->reversed ^= 1; //push to "children"
}

Recalc of size and other node parameters

int get_size(treap t){
    return t ? t->size : 0;
}
void recalc(treap t){
    if(!get_size(t)) return;
    t->size = get_size(t->l) + get_size(t->r)+1; //size

    //first and last elements
    lazy_pr(t); lazy_pr(t->l); lazy_pr(t->r);
    t->first_elem = t->l ? t->l->first_elem : t->val;
    t->last_elem = t->r ? t->r->last_elem : t->val;

    //non-increasing and non-decreasing properties
    bool lni=1, lnd=1, rni=1, rnd=1; //non-increasing/decreasing left and right subtrees
    if(t->l){ //unite this value with left subtree
        if(!t->l->non_incr || t->l->last_elem < t->val) lni=0;
        if(!t->l->non_decr || t->l->last_elem > t->val) lnd=0;
    }
    if(t->r){ //with right subtree
        if(!t->r->non_incr || t->r->first_elem > t->val) rni=0;
        if(!t->r->non_decr || t->r->first_elem < t->val) rnd=0;
    }
    t->non_incr = lni&&rni, t->non_decr = lnd&&rnd;
}

Split

void split(treap t, treap &l, treap &r, int pos, int tree_begin){
    if(!t) return void(l=r=0);
    lazy_pr(t);
    int val_pos = tree_begin + get_size(t->l);
    if(pos <= val_pos) split(t->l, l, t->l, pos, tree_begin), r=t;
    else split(t->r, t->r, r, pos, val_pos+1), l=t;
    recalc(l); recalc(r);
}

Merge

void merge(treap &t, treap l, treap r){
    lazy_pr(l); lazy_pr(r);
    if(!l || !r) t = l?l:r;
    else if(l->heap_val > r->heap_val) merge(l->r,l->r,r), t=l;
    else merge(r->l,l,r->l), t=r;
    recalc(t);
}

Build a treap from array

void build(vector<int> &a){
    for(int x:a) merge(root, root, new node(x));
}

Find k, the position of start LNIS

int find_k(treap t, int tree_end){
    lazy_pr(t);
    if(!t || t->non_incr) return tree_end - get_size(t); //return position before this tree
    int k = find_k(t->r, tree_end), val_pos = tree_end - get_size(t->r); //visit right subtree
    if(!t->r || (k == val_pos && t->r->first_elem <= t->val)) k--; //check value of the root
    lazy_pr(t->l);
    if(t->l && k == val_pos-1 && t->l->last_elem >= t->val){
        k = find_k(t->l, val_pos-1); //visit left subtree
    }
    return k;
}

Find the position of NLN

int find_nln(treap t, int x, int tree_begin){
    lazy_pr(t);
    if(!t) return tree_begin;
    if(t->val > x) return find_nln(t->l, x, tree_begin);
    return find_nln(t->r, x, tree_begin + get_size(t->l)+1);
}

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);
}

Comments (3)

Write comment?

Guslix

3 years ago, # |

The code has been changed and bugs are fixed

→ Reply

Andrei1998

I think there is also a simpler approach. Observe that queries really just add +1 or -1 to a counter (how far are we from the initial permutation). Therefore, we can compute the total balance added to the counter as a number; e.g. +23, or -13, or something like that, and then just use the classical algorithm to go forward 23 times or backward 13 times. It looks like amortized complexity is linear (although I haven't checked very carefully). However, this only solves "finding the last permutation after all operations are computed". Printing all of them along the way is too print-heavy, so let's say queries are of the form "what is the i-th position of the permutation after j steps" to make it manageable. This can also be solved offline by slightly-tweaking the approach above.

The more interesting idea is solving everything online: one can cache all permutations obtained using the above-defined balance as a key. To make storing the cache manageable I think you can represent permutations as a trie/prefix tree, where leaves represent permutations and edges are elements of the permutation. To reverse a suffix of a permutation (leaf) just walk the trie up to the reversal point and create a new chain with the new suffix in the trie starting there, essentially "sharing the common prefix". This makes space of the same order as time complexity and this idea might have some other usages?

3 years ago, # ^ |

Very interesting and advanced ideas. Of course, no need to explicitly make each permutation if isn't requiring to answer queries online.

Also my algorithm can support on each subsegment: sum, minimum, addition, assignment, etc.

Also it can overpower and such thing. Insert and delete many elements at once. Let be such queries among 100500 ones, and insert query makes many element with the same value. Also it's guaranteed that size of the array never don't exceed $$$k \cdot 10^5$$$. Let's create a "trash bucket" treap and move deleted nodes there. While insert query, saw off from the "trash bucket" a subtree of desired size, assign it with new value and merge into main treap in desired place

Guslix's blog

The Code