Ranking and Unranking k-subsequence universal words

Abstract

A subsequence of a word $w$ is a word $u$ such that $u=w[i_1]w[i_2],\dots w[i_{|u|}]$, for some set of indices $1\le i_1<i_2<\cdots <i_k\le |w|$. A word $w$ is $k$-subsequence universal over an alphabet $\Sigma$ if every word in ${\Sigma }^k$ appears in $w$ as a subsequence. In this paper, we provide new algorithms for $k$-subsequence universal words of fixed length $n$ over the alphabet $\Sigma =\{1,2,\dots ,\sigma \}$. Letting $\mathcal{U}(n,k,\sigma )$ denote the set of $n$-length $k$-subsequence universal words over $\Sigma$, we provide: * an $O(nk\sigma )$ time algorithm for counting the size of $\mathcal{U}(n,k,\sigma )$; * an $O(nk\sigma )$ time algorithm for ranking words in the set $\mathcal{U}(n,k,\sigma )$; * an $O(nk\sigma )$ time algorithm for unranking words from the set $\mathcal{U}(n,k,\sigma )$; * an algorithm for enumerating the set $\mathcal{U}(n,k,\sigma )$ with $O(n\sigma )$ delay after $O(nk\sigma )$ preprocessing.