Twori exist for odd-sized shorthand permutation windows with efficient generation
Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori
Discrete Mathematics
Summary
This paper looks at a special way to arrange permutations so that every possible sequence appears exactly once in a small, repeating grid called a tworus. The authors proved that such arrangements exist when the size of the permutations is an odd number and the tworus has two rows. They also found ways to make these twori very symmetrical and developed a method to create every next column in the grid quickly. In addition, they showed where such arrangements cannot exist and gave algorithms for related patterns in binary words.
What this means in practice
- •For combinatorial algorithm developers: Generate all permutations in fixed-size overlapping windows efficiently for mathematical and algorithmic applications.
- •For coding theorists: Use symmetrical twori constructions to design codes and combinatorial structures with unique pattern coverage.
A theory result. No direct application yet.
Authors
Tim Gerlach, Elizabeth Hartung, Pia Herkenrath, Joe Sawada, Aaron Williams
Abstract
A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when $n = 2m + 1$ is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into $2^{m-1}$ matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized $\mathcal{O}(1)$-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.