Boštjan Slivnik and Igor Rožanc
load balancing, generating combinations, combinatorial problems
A simple yet efficient load-balanced algorithm for generating a restricted set of combinations of k items taken from a set A of n items is described. The set can be restricted by a number of constraints each specifying that exactly (or at most, or at least) k' elements must be taken from a set A', for different k' < k and A' is a subset of A. The unrank procedure is not needed and we demonstrate that arbitrary precision arithmetic (operating on integers) can be avoided in most practical applications. The algorithm is thus suitable for computing environments with limited resources (like GPUs). The empirical evaluation of the algorithm is included.
Important Links:
Go Back
