New methods for the generation of permutations, combinations, and other combinatorial objects in parallel (Q2365578)

The paper gives results which have important theoretical meaning for a deep understanding a of the whole combinatorics, besides many technical results for supporting parallel processing are produced. The theoretical results create foundations for seeing combinatorics as the branch of mathematics dealing with choice functions of indexed families. It is shown that any set of permutations and combinations can be represented by a suitable set of choice functions of dedicated indeed families. It is also mentioned that any set of partitions or other combinatorial objects can be represented similarly. The investigation of layers and theorem 1 supply a general method for splitting any indexed family into subfamilies so that any choice function of the given family satisfying given requirements becomes a corresponding choice function of exactly one of its layer. The proof of theorem 5 reveals new relations between Pascal's triangle and combinations. The algorithm for the generation of the next specified choice function of indexed families has an important meaning as far as technical results are concerned. The results lead to develop parallel algorithms for generating regular and irregular sets of permutations or combinations both for MIMD and SIMD models. It is also worthwhile to mention that a new fast algorithm for finding any \(k\)-th combination of \(m\) out of \(n\) items has been given.