On the combinatorics of suffix arrays

• A new bijective combinatorial characterization of suffix array permutations is obtained.
• An existing characterization of Burrows–Wheeler transform can be advantageously applied to suffix arrays.
• A known suffix array characterization for binary alphabet is easily obtained through our approach.
• Known counting results can be obtained more simply with our characterization.

We present a bijective characterization of suffix array permutations obtained from a characterization of Burrows–Wheeler arrays given in [1]. We show that previous characterizations [2], [3] and [4], or their analogs, can be obtained in a simple and elegant way using this relationship. To demonstrate the usefulness of our approach, we obtain simpler proofs for some known enumeration results about suffix arrays [3]. Our characterization of suffix arrays is the first based on their relationship with Burrows–Wheeler permutations.