xiv. Permutation Constructions

Target	Construction	Exists iff
LIS $=a$, LDS $=b$	$a$ increasing blocks, each block decreasing, one block of size $b$	$a+b-1\le n\le ab$
exactly $k$ inversions (lexicographically smallest)	greedy: at each position take the smallest value that keeps $k$ reachable	$0\le k\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$
no two adjacent values consecutive	all evens, then all odds	$n=1$ or $n\ge 4$
all adjacent differences distinct	zigzag $1,n,2,n-1,\dots$	always
derangement	rotate by one: $p_i=i+1$, $p_n=1$	$n\ne 1$
$p_i\oplus i$ or $p_i+i$ conditions	pair $i$ with its complement inside a block of size $2^k$	depends on the condition
given cycle type	write the cycles consecutively	always
involution with $f$ fixed points	swap disjoint pairs	$f\equiv n(\mathrm{mod}2)$

LIS and LDS

vector<int> lisLdsPerm(int n, int a, int b) {  // LIS = a, LDS = b; empty if impossible
    if (a < 1 || b < 1 || a > n || b > n || a + b - 1 > n || (long long)a * b < n) return {};
    vector<int> sizes(a, 1); sizes[0] = b; int rest = n - b - (a - 1);
    for (int i = 1; i < a && rest > 0; i++) { int add = min(rest, b - 1); sizes[i] += add; rest -= add; }
    vector<int> p; int v = 0;
    for (int s : sizes) { for (int j = s; j >= 1; j--) p.push_back(v + j); v += s; }   // blocks decreasing inside, increasing across
    return p;
}

Proof: Erdős–Szekeres and the block construction

Necessity. Label each element with the length ${\ell }_i$ of the longest increasing subsequence ending at it. Elements with the same label form a decreasing subsequence (if $i<j$ and $p_i<p_j$ then ${\ell }_j>{\ell }_i$). There are at most $a$ labels, so some label class has at least $n/a$ elements, giving $n\le ab$. An increasing and a decreasing subsequence share at most one element, so $a+b-1\le n$. Sufficiency. With block sizes $s_1,\dots ,s_a$ (each $1\le s_i\le b$, one equal to $b$, total $n$), blocks with increasing value ranges and decreasing inside: an increasing subsequence takes at most one element per block, and one per block is possible, so LIS $=a$; a decreasing subsequence stays inside one block, so LDS $=\max s_i=b$. Such sizes exist exactly when $a+b-1\le n\le ab$. Verified against all permutations for $n\le 7$.

Exactly k inversions

vector<int> permWithInversions(int n, long long k) {   // exactly k inversions, 0 <= k <= n(n-1)/2
    vector<int> p; deque<int> rest;                    // place values n, n-1, ..., 1: value v can create up to v-1 inversions
    vector<int> pos;                                   // build by inserting: the largest value first
    for (int v = 1; v <= n; v++) rest.push_back(v);
    for (int i = 0; i < n; i++) {                      // position i: choose the smallest remaining value that keeps k reachable
        long long m = sz(rest) - 1;                    // the remaining suffix can still produce at most m(m-1)/2
        long long take = max(0LL, k - m * (m - 1) / 2);  // inversions this element must create (with smaller later ones)
        p.push_back(rest[take]); rest.erase(rest.begin() + take); k -= take;
    }
    return p;
}

Proof: the greedy gives the lexicographically smallest permutation with k inversions

If $m$ elements remain after the current position, they can create between $0$ and $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ inversions among themselves, any value in between. Placing the $t$-th smallest remaining value at the current position creates exactly $t$ inversions with later elements. So the current choice is feasible iff $k-t\in [0,(\genfrac{}{}{0ex}{}{m}{2})]$, and the smallest feasible $t$ is $\max (0,k-(\genfrac{}{}{0ex}{}{m}{2}))$, which the code takes. Choosing the smallest feasible value at every position gives the lexicographically smallest answer. Verified exhaustively for $n\le 7$.

No adjacent consecutive values

vector<int> noAdjacentConsecutive(int n) {     // |p[i+1] - p[i]| != 1; impossible for n = 2, 3
    if (n == 2 || n == 3) return {};
    vector<int> p;
    for (int v = 2; v <= n; v += 2) p.push_back(v);
    for (int v = 1; v <= n; v += 2) p.push_back(v);
    return p;
}

Proof: evens then odds works for n ≥ 4

Inside each half, neighbours differ by 2. At the junction the last even ($n$ or $n-1$) meets $1$; the difference is at least $3-1=2$ once $n\ge 4$. For $n=2,3$ a brute force shows no valid permutation (every arrangement of $1,2,3$ puts $2$ next to $1$ or $3$).

Related: Counting Fundamentals, Sequence DP (LIS).