Just another Perl shrine  
PerlMonks 
Re: Wordfeud racksby sundialsvc4 (Abbot) 
on Jul 30, 2013 at 17:11 UTC ( #1047075=note: print w/ replies, xml )  Need Help?? 
“All possible racks,” in such a game, is an infeasible number of possibilities to actually enumerate ... it would take weeks at best, if not months or centuries. But you don’t need to “list them, then count them,” in order to compute the probability of any given draw. If you first presume that “a unique draw” would be one in which the letters are always arranged in alphabetic order, so that AABA and ABAA are considered to be the same, then any particular draw could be equally expressed as a vector of 26 elements, such as (in this case) [3, 1, 0, 0 ...]. There are two rules to determine if a vector is valid: (a) the total of all elements in the vector must equal the total size of the draw, and (b) the value of the element in any given position must not exceed the defined total number of pieces for that position (letter). It is practical to construct a computer program to map out all of these combinations, since it is possible to eliminate billions of choices by recognizing as soon as possible when either of these two constraints have been exceeded. (As soon as you know that, cutshort the search.) Notice that there is nothing at all “random” about the algorithm. The probability of any given vector is simply 1/n, where n is the number of unique vectors that are found to exist. A similar technique can be used to solve the Eight Queens problem. It could be that what you’re actually interested in is: “given a valid vector v, how many arrangements of letters correspond to that vector?” This is a calculation that involves factorials (n!). The answer is [ F(v) ::= ( v[1]! * v[2]! * ... * v[n]! ) ] for any given vector v of size n, no matter which particular letters might be involved. Yes, having perfected the algorithm to give you the list of all possible vectors, with the help of bigint, you could also solve that problem. The denominator is [ SUM( f(v) ) for all v ], and the numerator is simply f(v).
In Section
Seekers of Perl Wisdom

