How to efficiently generate combinatorial structures such as posets, trees, B-trees, graphs, permutations, set partitions, Dyck paths, multisets or necklaces ... ? The Ruskey's book gives answers. It contains many surprising descriptions (and bibliographic references) of constant amortized time (CAT) and loopless algorithms.   > **CAT Algorithms** The holy grail of generating combinatorial objects is to find an algorithm that runs in Constant Amortized Time. This means that the amount of computation, after a small amount of preprocessing, is proportional to the number of objects that are listed. We do not count the time to actually output or process the objects; we are only concerned with the amount of data structure change that occurs as the objects are being generated.     _ Ruskey's book, page 8 _   > ** Loopless algorithm ** is an imperative algorithm that generates successive combinatorial objects, such as partitions, permutations, and combinations, in constant time and the first object in linear time     _ _
Sergey Kirgizov at 2020-06-09 22:01:49
Edited by Sergey Kirgizov at 2020-06-10 21:20:27

Please consider to register or login to comment on the paper.