Combinatorics

Description

This package provides basic combinatorial generators. Specifically

1. It generates all permutations of a given number of elements.
2. It generates all combinations k at a time from a set on n elements.

The Array and Integer classes have been extended with methods

 combinations(k)

and

 permutations()

Each of these methods will yield a sequence of arrays. For the Integer case, the arrays consist of the numbers (0..n-1). Thus 3.permutations will yield

 [0,2,1],[2,1,0],[1,0,2],[1,2,0],[2,0,1],[0,1,2]

For Arrays, the generated arrays will be re-arrangements or subsets of the original Array.

If the methods are called without a block, then the sequences are not generated. However, with or without a block the methods return the number of sequences that would be generated.

If there are invalid parameters, the methods return nil and do not attempt to generate any sequences.

Copyright

Copyright 2005 by Dale Brayden. Licensed under the same terms as Ruby.

Status

(2005/11/06) Beta. The code could use some clean-up.

Usage Examples

Show how many combinations or permutations there are

 puts 5.combinations(2)
 puts %w(a b c d f g).combinations(4)
 puts 6.permutations
 puts %w(a b c d f g).permutations

Generate combinations

 5.combinations(2) { |a| puts a.join(',') }
 puts %w(a b c d f g).combinations(4) { |a| puts a.join(',') }

Generate permutations

  4.permutations { |a| puts a.join(',') }
  puts %w(a b c d).permutations { |a| puts a.join(',') }

Required files