EV Combinations

[obi]

You have 127 EVs total (due to division by 4, it's easier to think of 127 than 512 with multiples of 4 being required... Just think of it as the points at level 100 rather than the EVs themselves), with no more than 63 allowed per stat. You have 6 stats to distribute them among. How many possible combinations of EVs are there? Keep in mind that you can invest anywhere between 0 and 63 in any given stat, and between 0 and 127 total.

That's just the Pokemon problem, however, and can be solved with a brute force algorithm. Consider the general problem:

You have A tokens, which cannot be distinguished from each other. You must distribute these tokens among B containers, labeled 1, 2, 3, ..., B - 1, B. Each container can hold, at most, C tokens. Not all tokens are required to be put in a container. Create an algorithm to determine the number of ways to distribute these tokens among the containers.

It seems that there are a few ways I can think of to attempt to solve this. Most of these can probably be used together.

First, assume that only 1 container will be used. The solution to this is trivial. The answer is either the number of tokens or the container's limit, whichever is smaller. Then assume exactly 2 containers will be used. The solution to this is also simple, especially when A is greater than 2 * B. Next assume exactly 3 containers will be used, and so on. Add up all your results and you have the answer. The problem is that at 3 containers or more (especially when you are unable to fill up all containers), this solution runs into some difficulties.

Another path to solving this is to simply ignore the limit per container and find out how many possibilities there are, or to ignore the limit of the number of tokens you have, and then calculate the possibilities. After you have this number, subtract out the illegal possibilities. To use the Pokemon problem as an example, assume there is no limit on how many EVs a Pokemon can get (so basically, stat exp. in RBY and GSC). Then there are 64 options for each container (because a container can be empty). There is then an upper limit of 64^6 possibilities for combinations, or 68,719,476,736, about 69 billion.

If you want to try an even more generalized problem, consider this extension: each container can be uniquely sized. For instance, container 1 can only hold 5 tokens, but container 2 can hold 26 tokens. You can actually use this in solving the other problems. Assume you must use all tokens, but you have an extra container that is the size of the number of tokens to distribute. Then, rather than having tokens "nowhere", you have them in this container, container 0.

 

[Kachalski]

Well, this is a big question. We are looking at 127 EVs which can only be distrebuted up to 63 in up to 6 containers. However, they can be unequal amounts? I'm quessing around 1,000 Billion combinations, but I would love to see somebody come up with an algebraic formula.

 

[obi]

There are significantly less than 69 billion combinations, actually. As I said in my post, I arrive at that number by assuming I have an infinite amount of EVs to distribute. Each stat then has 64 possibilities, and there are 6 stats, so 64^6 gives about 69 billion. In reality you have less than infinite EVs, and as such, some of those 69 billion are illegal.

 

[Tangerine]

We talked about this on IRC a while back. A friend of mine showed me this, which effectively solves the problem

 

[Kachalski]

Still, it comes to a point were we just go:

A: 1
B: 0
C: 0
D: 0
E: 0
F: 0

Repeated until every combination with 1 is completed, then:

A: 0
B: 1
C: 0
D: 0
E: 0
F: 0

I'm still saying there must be billions of combinations.

 

[obi]

The Stars and Bars method ignores the distinguishing feature of the EV system: Your containers can only hold so many tokens ("stars"). This is really what makes the problem difficult.

Kachalski: Yes, there are billions of combinations. The amount is much less than 69 billion, however.

 

[X-Act]

I once asked this exact same question in Congregation once, as a brain teaser. Let's see if I can dig up the thread.

EDIT: I had asked the Pokemon problem only here. Also, my problem assumed that you used ALL EVs. However, there I have the method I used to solve the brain teaser, which might help you in answering obi's subsequent questions.

 

[cantab]

We can treat this like a dice rolling problem. We roll 6 64-sided dice, with sides 0-63. We want the probability of rolling a total less than or equal to 127.

This program: http://www.fnordistan.com/smallroller.html

will calculate the probabilities. 6 D 64 add -1 apply to each die.

The chance of rolling 127 or less is 8.93%. The chance of rolling 127 exactly (ie a full EV allocation) is 0.36%

Now we just multiply the probabilities by the number of rolls, 64^6.

The number of possible effectively different EV spreads is 6.14 billion.
The number of possible effectively different fully-allocated EV spreads is 247 million. (This is the figure relevant to competitive use, you wouldn't leave EVs unallocated)

EDIT: F***ing NINJA'D

Still, my method is neat I think. It generalises well, especially to different sized boxes. I don't understand the mathematics behind the program however.

 

[X-Act]

The answer to the Pokemon case, considering 127 or less EVs can be put in each stat, is 6,137,312,896.

As I had highlighted in February 2008 in the brain teaser, if W_m,n is the number of ways to place m balls in exactly n boxes with a maximum limit of 63, then

W_m,n = Sum(W_{m-i},{n-1}) from i=1 to i=63. This assumes that W_0,0 = 1 and W_m,n = 0 for all m<0 and n<0.

The answer we need is then

Sum(6Cj x Sum(W_i,j)) where 6Cj is 6! / ((6 - j)! j!), i goes from 0 to 127 and j goes from 0 to 6.

For the general case, replace the numbers 63, 127 and 6 above with the corresponding numbers, of course.

 

[Brain]

We talked about this on IRC a while back. A friend of mine showed me this, which effectively solves the problem

More or less - this does not take caps into account.

If you use all EVs, you want to distribute n identical objects into k bins. If you may use less EVs than that, all you need to do is to add another bin, which will contain the objects you leave out. So we have n objects in k+1 bins. Which is like distributing n+k+1 objects in k+1 bins where each bin must contain at least one object. With n=127 and k=6 this gives us a figure of C(n+k, k) = C(133, 6).

Now, of course, this does not take any caps into account. But it's actually fairly easy to. It's easy to see that any illegal combination in the C(133, 6) combinations *must* be so that one, and only one, of the first six bins contains 64 or more EVs. So this is simple. First, *assume* that one bin contains 64 EVs: 63 EVs remain to distribute in 7 bins (6 stats + one leftover bin) and each such combination is illegal and included in the original C(133, 6) figure. This amounts to C(69, 6). Each of the six stats may be the one that overflows, hence we multiply by six and finally we subtract these illegal combinations. We are sure that no combination is subtracted twice because only one stat can overflow.

The answer is thus: C(n+k, k) - k*C(cap+k, k) = C(133, 6) - 6*C(69, 6) = 6,137,312,896

Now, to generalize: if we had to distribute 200 EVs with a cap of 49, it stands to reason that at least one stat would have to have upwards of 50 EVs. However, we do not have the luxury to assume that only one stat will be like that - up to four stats could overflow! Therefore, we have to proceed with caution to not subtract the same combinations more than once. I'm too lazy to write it all out, but it's just a matter of computing how many combinations have exactly floor(n/k) bins that overflow, then how many have exactly floor(n/k)-1 bins that overflow (the answer for floor(n/k) comes in handy), and subtract each figure times the number of ways to arrange these bins amongst all bins. It should be straightforward.