Module: Combinatorics::Choose

Defined in:
lib/combinatorics/choose/cardinality.rb,
lib/combinatorics/choose/mixin.rb

Overview

Author:

Since:

  • 0.4.0

Defined Under Namespace

Modules: Mixin

Class Method Summary collapse

Class Method Details

.C(n, r = nil) ⇒ Object

Note:

This method's naming convention reflects well-known notation used within fields of academic inquiry such as discrete mathematics and set theory. It represents a function returning an integer value for the cardinality of a k-combination (i.e. binomial coefficient.)

Wrapper for combination cardinality method defined above. The letter `C' is "chalkboard" notation for subset cardinality.

See Also:

Since:

  • 0.4.0



62
63
64
 
# File 'lib/combinatorics/choose/cardinality.rb', line 62

def self.C(n,r=nil)
  cardinality(n,r)
end

.cardinality(n, r = nil) ⇒ Fixnum

Compute the number of elements in a subset of given size

Examples:

cardinality(6, 4)
# => 15

Parameters:

  • n (Fixnum) —

    The number of elements in the input set

  • r (Fixnum) (defaults to: nil) —

    Cardinality of subsets to choose

Returns:

  • (Fixnum) —

    The binomial coefficient for "n-choose-r"

Raises:

  • (RangeError) —

    n must be non-negative.

  • (RangeError) —

    r must be non-negative.

  • (RangeError) —

    r must be less than or equal to n.

See Also:

Since:

  • 0.4.0



39
40
41
42
43
44
45
46
47
48
 
# File 'lib/combinatorics/choose/cardinality.rb', line 39

def self.cardinality(n,r=nil)
  raise(RangeError,"n must be non-negative") if n < 0

  case r
  when 0   then 1
  when nil then Math.factorial(n)
  else
    Math.factorial(n) / (Math.factorial(r) * Math.factorial(n - r))
  end
end

.cardinality_all(n, c = (1..n)) ⇒ Array

Note:

Sum of elements will equal Math.factorial(c)

Returns Elements are cardinalities for each subset "1" through "c".

Examples:

cardinality_all(4)
# => [4, 6, 4, 1]
cardinality_all(10, 5..10)
# => [252, 210, 120, 45, 10, 1]

Parameters:

  • n (Integer) —

    The total number of choices.

  • c (Enumerable) (defaults to: (1..n)) —

    The set of r values to choose from n.

Returns:

  • (Array) —

    Elements are cardinalities for each subset "1" through "c".

Raises:

  • (RangeError) —

    n must be non-negative.

See Also:

Since:

  • 0.4.0



93
94
95
96
97
98
99
 
# File 'lib/combinatorics/choose/cardinality.rb', line 93

def self.cardinality_all(n,c=(1..n))
  if n < 0
    raise(RangeError,"c must be non-negative")
  end

  c.map { |r| cardinality(n,r) }
end