lib/games_dice/probabilities.rb in games_dice-0.3.9 vs lib/games_dice/probabilities.rb in games_dice-0.3.10
- old
+ new
@@ -1,5 +1,7 @@
+require 'games_dice/prob_helpers'
+
# This class models probability distributions for dice systems.
#
# An object of this class represents a single distribution, which might be the result of a complex
# combination of dice.
#
@@ -17,10 +19,13 @@
# probs.max # => 12
# probs.expected # => 7.0
# probs.p_ge( 10 ) # => 0.16666666666666669
#
class GamesDice::Probabilities
+ include GamesDice::ProbabilityValidations
+ include GamesDice::ProbabilityCalcSums
+ extend GamesDice::ProbabilityCalcAddDistributions
# Creates new instance of GamesDice::Probabilities.
# @param [Array<Float>] probs Each entry in the array is the probability of getting a result
# @param [Integer] offset The result associated with index of 0 in the array
# @return [GamesDice::Probabilities]
@@ -28,16 +33,10 @@
# This should *probably* be validated in future, but that would impact performance
@probs = check_probs_array probs.clone
@offset = Integer(offset)
end
- # @!visibility private
- # the Array, Offset representation of probabilities.
- def to_ao
- [ @probs, @offset ]
- end
-
# Iterates through value, probability pairs
# @yieldparam [Integer] result A result that may be possible in the dice scheme
# @yieldparam [Float] probability Probability of result, in range 0.0..1.0
# @return [GamesDice::Probabilities] this object
def each
@@ -175,41 +174,32 @@
# results together.
# @param [GamesDice::Probabilities] pd_a First distribution
# @param [GamesDice::Probabilities] pd_b Second distribution
# @return [GamesDice::Probabilities]
def self.add_distributions pd_a, pd_b
- unless pd_a.is_a?( GamesDice::Probabilities ) && pd_b.is_a?( GamesDice::Probabilities )
- raise TypeError, "parameter to add_distributions is not a GamesDice::Probabilities"
- end
-
+ check_is_gdp( pd_a, pd_b )
combined_min = pd_a.min + pd_b.min
combined_max = pd_a.max + pd_b.max
- add_distributions_internal combined_min, combined_max, 1, pd_a, 1, pd_b
+ add_distributions_internal( combined_min, combined_max, 1, pd_a, 1, pd_b )
end
# Combines two distributions with multipliers to create a third, that represents the distribution
# created when adding weighted results together.
# @param [Integer] m_a Weighting for first distribution
# @param [GamesDice::Probabilities] pd_a First distribution
# @param [Integer] m_b Weighting for second distribution
# @param [GamesDice::Probabilities] pd_b Second distribution
# @return [GamesDice::Probabilities]
def self.add_distributions_mult m_a, pd_a, m_b, pd_b
- unless pd_a.is_a?( GamesDice::Probabilities ) && pd_b.is_a?( GamesDice::Probabilities )
- raise TypeError, "parameter to add_distributions_mult is not a GamesDice::Probabilities"
- end
-
+ check_is_gdp( pd_a, pd_b )
m_a = Integer(m_a)
m_b = Integer(m_b)
- combined_min, combined_max = [
- m_a * pd_a.min + m_b * pd_b.min, m_a * pd_a.max + m_b * pd_b.min,
- m_a * pd_a.min + m_b * pd_b.max, m_a * pd_a.max + m_b * pd_b.max,
- ].minmax
+ combined_min, combined_max = calc_combined_extremes( m_a, pd_a, m_b, pd_b ).minmax
- add_distributions_internal combined_min, combined_max, m_a, pd_a, m_b, pd_b
+ add_distributions_internal( combined_min, combined_max, m_a, pd_a, m_b, pd_b )
end
# Returns a symbol for the language name that this class is implemented in. The C version of the
# code is noticeably faster when dealing with larger numbers of possible results.
# @return [Symbol] Either :c or :ruby
@@ -223,27 +213,11 @@
# @return [GamesDice::Probabilities] new distribution
def repeat_sum n
n = Integer( n )
raise "Cannot combine probabilities less than once" if n < 1
raise "Probability distribution too large" if ( n * @probs.count ) > 1000000
- pd_power = self
- pd_result = nil
-
- use_power = 1
- loop do
- if ( use_power & n ) > 0
- if pd_result
- pd_result = GamesDice::Probabilities.add_distributions( pd_result, pd_power )
- else
- pd_result = pd_power
- end
- end
- use_power = use_power << 1
- break if use_power > n
- pd_power = GamesDice::Probabilities.add_distributions( pd_power, pd_power )
- end
- pd_result
+ repeat_sum_internal( n )
end
# Calculates distribution generated by summing best k results of n iterations
# of the distribution.
# @param [Integer] n Number of repetitions, must be at least 1
@@ -254,192 +228,17 @@
k = Integer( k )
raise "Cannot combine probabilities less than once" if n < 1
# Technically this is a limitation of C code, but Ruby version is most likely slow and inaccurate beyond 170
raise "Too many dice to calculate numbers of arrangements" if n > 170
check_keep_mode( kmode )
-
- if k >= n
- return repeat_sum( n )
- end
- new_probs = Array.new( @probs.count * k, 0.0 )
- new_offset = @offset * k
- d = n - k
-
- each do | q, p_maybe |
- next unless p_maybe > 0.0
-
- # keep_distributions is array of Probabilities, indexed by number of keepers > q, which is in 0...k
- keep_distributions = calc_keep_distributions( k, q, kmode )
- p_table = calc_p_table( q, p_maybe, kmode )
-
- (0...k).each do |n|
- keepers = [2] * n + [1] * (k-n)
- p_so_far = keepers.inject(1.0) { |p,idx| p * p_table[idx] }
- next unless p_so_far > 0.0
- (0..d).each do |dn|
- discards = [1] * (d-dn) + [0] * dn
- sequence = keepers + discards
- p_sequence = discards.inject( p_so_far ) { |p,idx| p * p_table[idx] }
- next unless p_sequence > 0.0
- p_sequence *= GamesDice::Combinations.count_variations( sequence )
- kd = keep_distributions[n]
- kd.each { |r,p_r| new_probs[r-new_offset] += p_r * p_sequence }
- end
- end
- end
- GamesDice::Probabilities.new( new_probs, new_offset )
+ repeat_n_sum_k_internal( n, k, kmode )
end
private
- def self.add_distributions_internal combined_min, combined_max, m_a, pd_a, m_b, pd_b
- new_probs = Array.new( 1 + combined_max - combined_min, 0.0 )
- probs_a, offset_a = pd_a.to_ao
- probs_b, offset_b = pd_b.to_ao
-
- probs_a.each_with_index do |pa,i|
- probs_b.each_with_index do |pb,j|
- k = m_a * (i + offset_a) + m_b * (j + offset_b) - combined_min
- pc = pa * pb
- new_probs[ k ] += pc
- end
- end
- GamesDice::Probabilities.new( new_probs, combined_min )
- end
-
- def check_probs_array probs_array
- raise TypeError unless probs_array.is_a?( Array )
- probs_array.map!{ |n| Float(n) }
- total = probs_array.inject(0.0) do |t,x|
- if x < 0.0 || x > 1.0
- raise ArgumentError, "Found probability value #{x} which is not in range 0.0..1.0"
- end
- t+x
- end
- if (total-1.0).abs > 1e-6
- raise ArgumentError, "Total probabilities too far from 1.0 for a valid distribution"
- end
- probs_array
- end
-
- def calc_keep_distributions k, q, kmode
- kd_probabilities = calc_keep_definite_distributions q, kmode
-
- keep_distributions = [ GamesDice::Probabilities.new( [1.0], q * k ) ]
- if kd_probabilities && k > 1
- (1...k).each do |n|
- extra_o = GamesDice::Probabilities.new( [1.0], q * ( k - n ) )
- n_probs = kd_probabilities.repeat_sum( n )
- keep_distributions[n] = GamesDice::Probabilities.add_distributions( extra_o, n_probs )
- end
- end
-
- keep_distributions
- end
-
- def calc_keep_definite_distributions q, kmode
- kd_probabilities = nil
- case kmode
- when :keep_best
- p_definites = p_gt(q)
- kd_probabilities = given_ge( q + 1 ) if p_definites > 0.0
- when :keep_worst
- p_definites = p_lt(q)
- kd_probabilities = given_le( q - 1 ) if p_definites > 0.0
- end
- kd_probabilities
- end
-
- def calc_p_table q, p_maybe, kmode
- case kmode
- when :keep_best
- p_kept = p_gt(q)
- p_rejected = p_lt(q)
- when :keep_worst
- p_kept = p_lt(q)
- p_rejected = p_gt(q)
- end
- [ p_rejected, p_maybe, p_kept ]
- end
-
- # Convert hash to array,offset notation
- def self.prob_h_to_ao h
- rmin,rmax = h.keys.minmax
- o = rmin
- s = 1 + rmax - rmin
- raise ArgumentError, "Range of possible results too large" if s > 1000000
- a = Array.new( s, 0.0 )
- h.each { |k,v| a[k-rmin] = Float(v) }
- [a,o]
- end
-
- # Convert array,offset notation to hash
- def self.prob_ao_to_h a, o
- h = Hash.new
- a.each_with_index { |v,i| h[i+o] = v if v > 0.0 }
- h
- end
-
def calc_expected
total = 0.0
@probs.each_with_index { |v,i| total += (i+@offset)*v }
total
end
- def check_keep_mode kmode
- raise "Keep mode #{kmode.inspect} not recognised" unless [:keep_best,:keep_worst].member?( kmode )
- end
-
end # class GamesDice::Probabilities
-
-# @!visibility private
-# Helper module with optimised Ruby for counting variations of arrays, such as those returned by
-# Array#repeated_combination
-#
-# @example How many ways can [3,3,6] be arranged?
-# GamesDice::Combinations.count_variations( [3,3,6] )
-# => 3
-#
-# @example When prob( a ) and result( a ) are same for any arrangement of Array a
-# items = [1,2,3,4,5,6]
-# items.repeated_combination(5).each do |a|
-# this_result = result( a )
-# this_prob = prob( a ) * GamesDice::Combinations.count_variations( a )
-# # Do something useful with this knowledge! E.g. save it to probability array.
-# end
-#
-module GamesDice::Combinations
- @@variations_cache = {}
- @@factorial_cache = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
-
- # Counts variations of an array. A unique variation is an arrangement of the array elements which
- # is detectably different (using ==) from any other. So [1,1,1] has only 1 unique arrangement,
- # but [1,2,3] has 6 possibilities.
- # @param [Array] array List of things that can be arranged
- # @return [Integer] Number of unique arrangements
- def self.count_variations array
- all_count = array.count
- group_sizes = group_counts( array )
- cache_key = all_count.to_s + ":" + group_sizes.join(',')
- @@variations_cache[cache_key] ||= variations_of( all_count, group_sizes )
- end
-
- private
-
- def self.variations_of all_count, groups
- all_arrangements = factorial( all_count )
- # The reject is an optimisation to avoid calculating and multplying by factorial(1) (==1)
- identical_arrangements = groups.reject {|x| x==1 }.inject(1) { |prod,g| prod * factorial(g) }
- all_arrangements/identical_arrangements
- end
-
- # Returns counts of unique items in array e.g. [8,8,8,7,6,6] returns [1,2,3]
- # Sort is for caching
- def self.group_counts array
- array.group_by {|x| x}.values.map {|v| v.count}.sort
- end
-
- def self.factorial n
- # Can start range from 2 because we have pre-cached the result for n=1
- @@factorial_cache[n] ||= (2..n).inject(:*)
- end
-end