Ranking and Unranking k-subsequence universal words

A subsequence of a word $w$ is a word $u$ such that $u=w[i_1]w[i_2],\dots w[i_{\mathrm{\mid }u\mathrm{\mid }}]$, for some set of indices $1\le i_1<i_2<\cdots <i_k\le \mathrm{\mid }w\mathrm{\mid }$. A word $w$ is $k$-subsequence universal over an alphabet $\mathrm{\Sigma }$ if every word in ${\mathrm{\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 $\mathrm{\Sigma }=\{1,2,\dots ,\sigma \}$. Letting $\mathcal{U}(n,k,\sigma )$ denote the set of $n$-length $k$-subsequence universal words over $\mathrm{\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.