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.
Abstract:
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.
-
The postscript file is 301,862 bytes,
the dvi file is 76,832 bytes.
-
Please send
me a note
if you download a copy -- Thanks!
-
Presented at 2?th S.E. Conference on Combinatorics, Graph
Theory, and Computing.
-
Appears in SIAM J. Discrete Mathematics,
11 (1998) 94-109.
-
Typo: In the Pascal program of Figure 2.1, the
Mr should be M. It is the M set
being generated, not the MR set, in
agreement with (8). [Thanks to Tom Spreen for noticing this typo.]
-
Malcolm Smith is now at Camosun College, Victoria, B.C.
-
Malcolm Smith is now at the Dominion Royal Observatory, Saanich, B.C.
-
MR 99b:68100 (68Q25 (05A15 05C30 68R05 68R15)).
Selected Citations
-
Stephen Swift, Allan Tucker, Jason Crampton, and David Garway-Heath,
An improved restricted growth function genetic algorithm
for the consensus clustering of retinal nerve fibre data,
Proceedings of the 9th annual conference on Genetic and
evolutionary computation,
London, England
SESSION: Real-world applications:
Pages: 2174 - 2181
Year of Publication: 2007
ISBN:978-1-59593-697-4.
-
Allan Tucker, Jason Crampton, and Stephen Swift,
RGFGA: An Efficient Representation and Crossover for Grouping
Genetic Algorithms,
Evolutionary Computing, 13 (2006) 477-499.
-
Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski,
and Prabhakar Ragde,
Embeddings of k-connected graphs of pathwidth k,
Discrete Applied Mathematics
Volume 145, Issue 2, 15 January 2005, Pages 242-265.
-
A. Proskurowski and J.A. Telle,
Classes of graphs with restricted interval models,
Discrete Mathematics and Theoretical Computer Science,
3, 1999, 167-176.
Back to list of publications.
