Decoding universal cycles for t-subsets and t-multisets by decoding bounded-weight de Bruijn sequences
This work addresses a bottleneck in combinatorial algorithms for researchers in computer science and mathematics by providing efficient decoding methods where few existed before, though it is incremental as it builds on known constructions.
The paper tackled the problem of efficiently decoding universal cycles for t-subsets and t-multisets by developing the first polynomial time/space decoding algorithms for bounded-weight de Bruijn sequences, which were then applied to achieve efficient decoding for these combinatorial objects.
A universal cycle for a set S of combinatorial objects is a cyclic sequence of length |S| that contains a representative of each element in S exactly once as a substring. Despite the many universal cycle constructions known in the literature for various sets including k-ary strings of length n, permutations of order n, t-subsets of an n-set, and t-multisets of an n-set, remarkably few have efficient decoding (ranking/unranking) algorithms. In this paper we develop the first polynomial time/space decoding algorithms for bounded-weight de Bruijn sequences for strings of length nover an alphabet of size k. The results are then applied to decode universal cycles for t-subsets and t-multisets.