Rank and unrank increasing arrangements

Question

i want to rank and to unrank increasing Arrangements. See following example:

n := 3 (permutation elements: 1-n)
b := 2 (barriers: 0s)

valid:
rank 0: 0,0,1,2,3
rank 1: 0,1,0,2,3
rank 2: 0,1,2,0,3
rank 3: 0,1,2,3,0
rank 4: 0,1,3,0,2
....


invalid:
0,3,2,1,0
0,3,0,2,1
...

You can see that 0 is a barrier and between 2 barriers the permutation elements are must be increasing.

How many arrangements exists with n permutation elements and b barriers?

How to rank/unrank such an arrangement? (the rank of an arrangement is the index number of all valid arrangements, written in some order)

Currently I do bruteforce but usually my b is 3-255 so its not an option to bruteforce.

Thanks in advance.

Answer 1

I don't have a solution for rank/unrank, but I do have a quick algorithm for your first question ("How many arrangements exists with n permutation elements and b barriers?"), which will hopefully help someone create a fast algorithm for rank/unrank.

from math import comb, factorial
from functools import lru_cache


@lru_cache
def stirling(n, k):
    if n == k:
        return 1
    if n == 0 or k == 0:
        return 0
    if k == 2:
        return 2**(n-1) - 1
    if n == k - 1:
        return comb(n, 2)
    return k * stirling(n-1, k) + stirling(n-1, k-1)
    
def star_and_bar(stars, bars):
    return comb(stars+1, bars)
    
def count_valid(n, b):
    return sum(factorial(groups)*stirling(n, groups)*star_and_bar(b, groups)
            for groups in range(min(b+1, n)+1))

I count the number of ways to partition the n numbers into k unordered sets (stirling numbers of the second kind). I multiply this by the number of ways to order these sets (factorial groups) and multiply by the number of ways to intersperse barrier 0's (modified stars and bars problem, where bars can exist on the outside, but not adjacent to each other). Note that I'm treating the set of numbers as the bar, not the 0's. I then sum these products over all valid k.

-- Update --

I had shared the problem with a friend of mine, @ForgotMyName, who was able to offer further mathematical insight. He noted that there's an even more elegant solution for counting arrangements- merely (barriers+1) ** elements, or in python:

def count_valid(n, b):
    return (n + 1) ** b

Much more elegant than my solution.