module Combinatorial

Combinatorial Calculation Library

by Shin-ichiro Hara

Version 2.0 (2001.09.14)

Public Class Methods

comb(n, m = n) { || ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 32
def comb(n, m = n)
  if m == 0
    yield([])
  else
    comb(n, m - 1) do |x|
      (((x[0] || -1) + 1)...n).each do |i|
        yield([i] + x)
      end
    end
  end
end
perm(n, m = n) { || ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 20
def perm(n, m = n)
  if m == 0
    yield([])
  else
    perm(n - 1, m - 1) do |x|
      (0...n).each do |i|
        yield([i] + x.collect{|j| j < i ? j : j + 1})
      end
    end
  end
end
perm0(n, stack = []) { |y;| ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 62
def perm0(n, stack = [])
  (0...n).each do |x|
    unless stack.include? x
      stack.push x
      if stack.size < n
        perm0(n, stack) do |y|; yield y; end
      else
        yield stack.self
      end
      stack.pop
    end
  end
end
power(n, m = n) { || ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 8
def power(n, m = n)
  if m == 0
    yield([])
  else
    power(n, m - 1) do |x|
      (0...n).each do |i|
        yield([i] + x)
      end
    end
  end
end
power0(n, m = n) { |0...m.collect{ (i, = divmod n).last }| ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 56
def power0(n, m = n)
  0.upto n**m-1 do |i|
    yield( (0...m).collect{ (i, = i.divmod n).last } )
  end
end
rep_comb(n, m) { || ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 44
def rep_comb(n, m)
   if m == 0
     yield([])
   else
     rep_comb(n, m - 1) do |x|
       ((x.empty? ? 0 : x.last)...n).each do |i|
        yield(x+[i])
       end
     end
   end
end

Private Instance Methods

comb(n, m = n) { || ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 32
def comb(n, m = n)
  if m == 0
    yield([])
  else
    comb(n, m - 1) do |x|
      (((x[0] || -1) + 1)...n).each do |i|
        yield([i] + x)
      end
    end
  end
end
perm(n, m = n) { || ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 20
def perm(n, m = n)
  if m == 0
    yield([])
  else
    perm(n - 1, m - 1) do |x|
      (0...n).each do |i|
        yield([i] + x.collect{|j| j < i ? j : j + 1})
      end
    end
  end
end
perm0(n, stack = []) { |y;| ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 62
def perm0(n, stack = [])
  (0...n).each do |x|
    unless stack.include? x
      stack.push x
      if stack.size < n
        perm0(n, stack) do |y|; yield y; end
      else
        yield stack.self
      end
      stack.pop
    end
  end
end
power(n, m = n) { || ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 8
def power(n, m = n)
  if m == 0
    yield([])
  else
    power(n, m - 1) do |x|
      (0...n).each do |i|
        yield([i] + x)
      end
    end
  end
end
power0(n, m = n) { |0...m.collect{ (i, = divmod n).last }| ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 56
def power0(n, m = n)
  0.upto n**m-1 do |i|
    yield( (0...m).collect{ (i, = i.divmod n).last } )
  end
end
rep_comb(n, m) { || ... } click to toggle source
# File lib/algebra/combinatorial.rb, line 44
def rep_comb(n, m)
   if m == 0
     yield([])
   else
     rep_comb(n, m - 1) do |x|
       ((x.empty? ? 0 : x.last)...n).each do |i|
        yield(x+[i])
       end
     end
   end
end