Premium
A generic approach for the unranking of labeled combinatorial classes
Author(s) -
Martínez Conrado,
Molinero Xavier
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10025
Subject(s) - struct , combinatorial analysis , rank (graph theory) , combinatorial method , combinatorial algorithms , order (exchange) , mathematics , combinatorics , combinatorial optimization , computer science , algorithm , finance , economics , programming language
In this article, we design and analyze algorithms that solve the unranking problem (i.e., generating a combinatorial structure of size, n given its rank) for a large collection of labeled combinatorial classes, those that can be built using operators like unions (+), products (⋆), sequences, sets, cycles, and substitutions. We also analyze the performance of these algorithms and show that the worst‐case is ( n 2 ) (( n log n ) if the so‐called boustrophedonic order is used), and provide an algebra for the analysis of the average performance and higher‐order moments together with a few examples of its application. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 472–497, 2001
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom