A note on combination generators

ABSTRACT

A recent study by Akl indicates that Mifsud's algorithm, which involves unnecessary searching operations, is the fastest existing combination generator. A modified Page and Wilson's algorithm, which is essentially similar to Mifsud's algorithm, is presented. A theoretical analysis of the modified algorithm is also given.

REFERENCES

• 1: Selim G. Akl, A Comparison of Combination Generation Methods, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.42-45, March 1981 [doi>10.1145/355934.355937]
• 2: Charles J. Mifsud, Algorithm 154: combination in lexicographical order, Communications of the ACM, v.6 n.3, p.103, March 1963 [doi>10.1145/366274.366309]
• 3: PAGE, E. S., AND WILSON L.B. An Introduction to Computational Combinatorics. Cambridge Computer Science Text 9, Cambridge University Press, 1979, p. 117.
• 4: Edward M. Reingold , Jurg Nievergelt , Narsingh Deo, Combinatorial Algorithms: Theory and Practice, Prentice Hall College Div, 1977

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms

Keywords:
combinations