Re: Wordfeud racks

“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, cut-short 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).

Replies are listed 'Best First'.
Re^2: Wordfeud racks by Laurent_R (Canon) on Jul 30, 2013 at 22:15 UTC
“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. I don't think so. Even assuming the worse-case scenario that the bag has at least 7 copies of each letter, the number of possible ordered racks is at most 26**7, or about 8 billion (we absolutely do not care whether the A that you get is A1, or A2, or A3..., it is just an A). This is admitedly a big number, but you certainly don't need weeks (let alone centuries) to list them all on a computer by the standards of today. And the actual number of racks is in fact much smaller for two reasons: some letters have only possibly two or three copies and that reduces quite drastically the number of actual possibilities, and many racks are actually equivalent (permutations of another one). I do not have enough information on the game to compute everything, but I would be surprised if the number of actually different racks would exceed a couple of millions. So at most a few seconds to enumerate them all on a modern computer.	[reply]
Re^3: Wordfeud racks by choroba (Cardinal) on Jul 31, 2013 at 08:33 UTC
a couple of millions Please, see Re^2: Wordfeud racks. a few seconds to enumerate them all And Re^2: Wordfeud racks also. Update: You were right. See Re: Wordfeud racks. لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ	[reply]
Re^4: Wordfeud racks by Laurent_R (Canon) on Jul 31, 2013 at 23:28 UTC
Thank you for your update choroba. I upvoted your post for this (I had not seen your post before the update, but if I had, I would have most probably neither upvoted not downvoted it at the time, I was only expressing a relatively well informed opinion, certainly not a certainty, and there was a possibility that I goofed it completely). I actually made some calculations, but with a number of very rough hypotheses on the letter distribution, my rough initial estimate on the number of unique racks was about 1.7 million, which is why I came up with a couple of million estimate. It seems that the number of possible racks is slightly less 3.2 million, so I was off by almost a factor of 2. But, still, the right order of magnitude, much closer than other estimates. Not too bad, in the end.	[reply]