On random and adaptive parallel generation of combinatorial objects

Abstract

This paper describes functions mapping the interval [0 .. 1) into the set of combinatorial objects of certain kind, e.g. permutations, combinations, binary and t-ary trees, subsets, variations, combinations with repetitions, permutations of combinations and composition of integers. These mappings can be used for generating these objects at random, with equal probability of each object to be chosen. The novelty of the technique is that it avoids the use of very large integers and applies the random number generator only once at the same time (known methods either use counters that are exponential in the size of objects or make use of a series of random numbers). The advantage of the new method is that it can be applied for both random object generation and dividing all objects into desirable sized groups. The latter is exploited in designing adaptive algorithm for generating all combinations, permutationst-ary trees, or variations, on a parallel model of computation, where an algorithm runs adaptively if it can be implemented on a model with arbitrary number of available processors.

Keywords:

• Random generation
• combinatorial objects
• lexicographic order
• adaptive parallel algorithms

C.R. Categories:

• G.2.1 Combinatorial algorithms
• permutations and combinations
• G.2.2 Trees
• G.3 Randam number generation

¹This research is supported by national science and engineering research council of canada.

¹This research is supported by national science and engineering research council of canada.

Notes

¹This research is supported by national science and engineering research council of canada.