Analysis of Algorithms for Listing Equivalence Classes of k -ary Strings
Andrzej Proskurowski, Frank Ruskey, Malcolm J. Smith · SIAM Journal on Discrete Mathematics · 1998
We give efficient algorithms for listing equivalence classes of k-ary strings under reversal and permutation of alphabet symbols. As representative of each equivalence class, we choose that string which is lexicographically smallest. These algorithms use space O(n) and time $O(\sqrt{k} N)$, where N is the total number of strings generated and n is the length of each string. For k = 2, we obtain a recursive decomposition of the set of binary strings that allows the strings to be generated without rejecting any strings. For $k \ge 3$, some strings must be rejected. The algorithm is simple but its exact analysis is rather complicated. In the analysis we determine a quantity of independent interest---the average length of the common prefix of two randomly chosen infinite length "restricted-growth" strings.