Class Combinations
In: combinations.rb
Parent: Object

Methods

combinations   each   new  

Public Class methods

new(n, k)

[Source]

# File combinations.rb, line 22
        def initialize(n, k)
                @n = n
                @k = k
        end

Public Instance methods

each() {|a| ...}

Yield a sequence of combinations taken k at a time from the set (0..n-1). Return the number of such combinations. Return nil if the parameters are invalid. If no block is given, then the actual sequence is not generated.

[Source]

# File combinations.rb, line 29
        def each
                return nil if @n < 0 or @k > @n or @k < 0
                ret = @n.combinations_count(@k)
                return ret if not block_given?
                if @k <= @n / 2
                        combinations(@n, @k) { |a| yield a}
                else
                        elems = [].sequence(0,@n - 1)
                        combinations(@n, @n - @k) { |a| yield elems - a}
                end
                ret
        end

Private Instance methods

combinations(n, k) {|[]| ...}

Yields the sequence of combinations of (0..n-1) taken k at a time. The parameter k must be <= n / 2.

The algorithm is to yield the trivially-obtained results for k = 0 or 1. If k > 1, then yield the sequences of combinations of k-1 items + a new item for the new item taken from k-1 to n-1.

[Source]

# File combinations.rb, line 50
        def combinations(n, k)
                if k == 0
                        yield []
                elsif k == 1
                        (n-1).downto(0) { |i| yield [i] }
                else
                        (n-1).downto(k-1) do |i|
                                combinations(i, k - 1) { |a| yield a << i }
                        end
                end
        end

[Validate]