Analysis of Algorithms for Listing Equivalence Classes of k-ary Strings

Andrzej Proskurowski, Department of Computer and Information Science, University of Oregon, USA.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Malcolm Smith, Department of Computer Science, University of Victoria, Canada.


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 >= 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.

Keywords: Combinatorial generation, k-ary strings, Stirling numbers, restricted growth function, k-paths.
AMS Classification: 05A15, 05C30, 60J10, 68Q25, 68R05, 68R15.

Selected Citations

Back to list of publications.