5
\$\begingroup\$

This code finds expectation and standard deviation of sum(x) of 6 digited base-49 numbers with all digits distinct.

The expectation is: \$\mu={\rm E[X]}=\frac1n\sum_{k=0}^{n}x_i=\frac{x_1+x_2+\ldots+x_n}{n}\$
whereas standard deviation is: \${\rm \sigma[X]}=\sqrt{{\rm E[(X-\mu)^2]}}=\sqrt{\frac1n[(x_1-\mu)^2+(x_2-\mu)^2+\ldots+(x_n-\mu)^2]}\$

package test;

import java.util.ArrayList;
import java.util.Arrays;

public class BallsSum {
final static int BALLS_DRAWN = 3;
final static int TOTAL_BALLS = 49;

public static void main(String args[]) {
    long startTime = System.nanoTime();
    int mNumberOfWays = 0;
    int mTotalSum = 0;

    ArrayList<Integer> mOneDrawPartialSums = new ArrayList<Integer>();

    BallCombination mBallCombination = new BallsSum().new BallCombination();

    int MAX_POSSIBLE_COMB = 1;
    for (int i = 0; i < BALLS_DRAWN; i++) {
        MAX_POSSIBLE_COMB *= (TOTAL_BALLS - i);
    }
    for (int i = 0; i < MAX_POSSIBLE_COMB; i++) {
        ++mNumberOfWays;
        mOneDrawPartialSums.add(mBallCombination.getSum());
        mTotalSum += mBallCombination.getSum();
        mBallCombination.getNewCombination();
    }

    float mExpectationValue = mTotalSum / mNumberOfWays;
    System.out.println("Expectation value is " + mExpectationValue);

    int mStandardDeviationSum = 0;
    for (int i = 0; i < mOneDrawPartialSums.size(); i++) {
        mStandardDeviationSum += Math.pow(
                (mOneDrawPartialSums.get(i) - mExpectationValue), 2);
    }

    float mStandardDeviation = (float) Math.sqrt(mStandardDeviationSum
            / mNumberOfWays);
    System.out.println("Standard Deviation is " + mStandardDeviation);
    long endTime = System.nanoTime();
    System.out.println("Took "+(endTime - startTime) + " ns"); 
}

public class BallCombination {

    int[] mCombination;
    ArrayList<int[]> mFormedCombinations;

    public BallCombination() {
        this.mCombination = new int[BALLS_DRAWN];
        for (int i = 0; i < BALLS_DRAWN; i++) {
            this.mCombination[i] = i + 1;
        }

        this.mFormedCombinations = new ArrayList<int[]>();
        this.mFormedCombinations.add(this.mCombination);
    }

    public void print() {
        System.out.print("(");
        for (int i = 0; i < BALLS_DRAWN; i++) {
            System.out.print(this.mCombination[i]);
            if (i != BALLS_DRAWN - 1) {
                System.out.print(",");
            }
        }
        System.out.println(")");
    }

    public boolean getNewCombination() {
        for (int i = 0; i < BALLS_DRAWN; i++) {
            if (this.mCombination[i] < TOTAL_BALLS) {
                ++this.mCombination[i];
                // Debug printing System.out.print("newComb:");
                print();
                if (isUnique(this.mCombination)) {
                    mFormedCombinations.add(mCombination);
                    return true;
                }
            } else {
                this.mCombination[i] = 1;
            }
        }
        return false;
    }

    private boolean isUnique(int[] pCombination) {
        if (containsDuplicate(pCombination)) {
            return false;
        }
        for (int i = 0; i < mFormedCombinations.size(); i++) {
            if (sort(mFormedCombinations.get(i)).equals(sort(pCombination))) {
                return false;
            }
        }
        return true;
    }

    private int[] sort(int[] pArray) {
        Arrays.sort(pArray);
        return pArray;
    }

    private boolean containsDuplicate(int[] pCombination) {
        for (int i = 0; i < pCombination.length; i++) {
            for (int j = i + 1; j < pCombination.length; j++) {
                if (pCombination[i] == pCombination[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public int getSum() {
        int sum = 0;
        for (int i = 0; i < this.mCombination.length; i++) {
            sum += this.mCombination[i];
        }
        return sum;
    }
}
}

I'm not sure if this is correct way to do this because i want to calculate it for BALLS_DRAWN=6 that may take hours with this code because exponential interpolation of the time required for the task from 1,2,3 and 4 balls drawn is 6 hrs, see this and this, but console shows out of memory error for 5 only. :D

\$\endgroup\$
  • \$\begingroup\$ This question needs more detail about how the balls are selected. Is this a lottery-style "selection", or is it just distinct selections? \$\endgroup\$ – rolfl Apr 7 '15 at 21:19
  • \$\begingroup\$ @rolfl NO REPLACEMENT SHOULD EXPLAIN IT ALL \$\endgroup\$ – RE60K Apr 8 '15 at 5:49
8
\$\begingroup\$

I am sure there is a better way to compute the value mathematically, but brute-forcing the solution is quite a lot faster than the 6 hours you suggest.... I have 49/6 down to less than 2 seconds on my laptop... how is this done?

Firstly, math is your friend. There are a fixed number of combinations that are possible:

\$Cn = 49 \times 48 \times 47 \times 46 \times 45 \times 44\$

This computes to 10,068,347,520. These 10 billion combinations do not take in to account that the ball order of selection is not significant. Since there are 720 ways (6 * 5 * 4 * 3 * 2 * 1) to order 6 balls, there are really only 10bil / 720 sequences, (about 14 million - 13,983,816) of balls that are possible. These can actually be brute-forced.

To brute-force efficiently, use primitives, no objects (and garbage collection)! Here's how to brute it - count the number of times each sum-of-balls happens.

  1. the maximum sum will come from the combination [44,45,46,47,48,49]
  2. create an array with space to count sum instances up to that magnitude
  3. start with a collection of N=6 balls [1,2,3,4,5,6] with an upper limit of value 49.
  4. record that sum in the count:

    sum = 6 + 5 + 4 + 3 + 2 + 1;
    counts[sum]++;
    
  5. 'increment' the ball combination using some intelligence (in this case, increment to [1, 3, 4, 5, 6, 7] - and then to [2, 3, 4, 5, 6, 7] and so on)

  6. increment the counter for the sum of each combination as you go.

At this point, you have an array of counts... where the index is the sum, and the value in the array is the number of times that sum was encountered.

For example, for 2 balls of maximum 6, the counts are:

sum   ->  0  1  2  3  4  5  6  7  8  9 10 11
count ->  0, 0, 0, 1, 1, 2, 2, 3, 2, 2, 1, 1

at sum 3, that would be ball 1 and 2 (sum to 3). ball 1 and 3 sum to 4, balls 1 and 4, as well as 2, and 3 sum to 5, and so on.

Now, with this data, it is easy to calculate the mean, and standard deviations.... I used some Java 8 streams to do it...

final long count = LongStream.of(counts).sum();
final long total = IntStream.range(0, counts.length)
        .mapToLong(index -> index * counts[index])
        .sum();
final double mean = total / (double)count;

The standard deviation required a little helper function which takes a deviation, and a count, and squares the deviation, and multiplies by the count:

private static double valDev(final double diff, final long count) {
    return diff * diff * count;
}

We can use that function to calculate the total deviations:

final double dev = IntStream
    .range(0, counts.length)
    .mapToDouble(index -> valDev(index - mean, counts[index]))
    .sum();

The, with that total deviation, the Std. deviation is just:

final double sd = Math.sqrt(dev / count);

Putting all of this logic together, you get:

private static final long[] countComboSums(final int balls, final int base) {
    int size = 1;
    int[] state = new int[balls];
    for (int i = 0; i < balls; i++) {
        size += base - i;
        state[i] = i + 1;
    }
    long[] ret = new long[size];
    final int max = base - balls + 1;
    do {
        logState(state, balls, ret);
    } while (increment(state, max));
    return ret;
}

private static boolean increment(int[] state, int max) {
    if (++state[0] > max) {
        return false;
    }
    int c = 1;
    while (c < state.length && state[c - 1] == state[c]) {
        state[c++]++;
    }
    c--;
    while (--c >= 0) {
        state[c] = c + 1;
    }
    return true;
}

private static void logState(int[] state, int balls, long[] ret) {
    ret[IntStream.of(state).sum()]++;
}

private static void processCombo(int base, int balls) {
    long nanos = System.nanoTime();
    final long[] counts = countComboSums(balls, base);
    final long count = LongStream.of(counts).sum();
    final long total = IntStream.range(0, counts.length)
            .mapToLong(index -> index * counts[index]).sum();
    final double mean = total / (double) count;
    final double dev = IntStream
            .range(0, counts.length)
            .mapToDouble(index -> valDev(index - mean, counts[index]))
            .sum();
    final double sd = Math.sqrt(dev / count);
    nanos = System.nanoTime() - nanos;
    System.out.printf("For base %d with %d balls in %.3fs, mean is %.3f (sd %.3f) counts are %s\n",
            base, balls, nanos / 1000000000.0, mean, sd, Arrays.toString(counts));
}

private static double valDev(final double diff, final long count) {
    return diff * diff * count;
}

public static void main(String[] args) {
    for (int i = 6; i <= 49; i++) {
        for (int b = 1; b <= 6; b++) {
            processCombo(i, b);
        }
    }
}

For me, this produces output similar to:

.....
For base 48 with 6 balls in 1.709s, mean is 147.000 (sd 32.078) counts are 
For base 49 with 1 balls in 0.000s, mean is 25.000 (sd 14.142) counts are 
For base 49 with 2 balls in 0.000s, mean is 50.000 (sd 19.791) counts are 
For base 49 with 3 balls in 0.002s, mean is 75.000 (sd 23.979) counts are 
For base 49 with 4 balls in 0.029s, mean is 100.000 (sd 27.386) counts are 
For base 49 with 5 balls in 0.264s, mean is 125.000 (sd 30.277) counts are 
For base 49 with 6 balls in 1.933s, mean is 150.000 (sd 32.787) counts are 

Though, having done all this, I am pretty sure there's a mathematical way to do the same process much faster still.... I'm just not sure what it is.

\$\endgroup\$
7
\$\begingroup\$

Response to current solution

You have correctly calculated the number of combinations and permutations that are available. See this output from Excel (which has built-in functions for this):

Excel output

However I disagree with the conclusion that we are interested in the number of combinations. My understanding of the question is that \$[1, 2, 3, 4, 5, 6]\$ is a different number to \$[2, 1, 3, 4, 5, 6]\$ and both should be counted. If you are doing some complex calculation to only count one of these variations and account for the other combinations, you lost me.

Calculation of the expected value

Basically you want an expression for the sum of all the available numbers.

Looking at the question, it seems to be a problem that is set for a university course, so I am reluctant to provide code directly. But here is how I see the the problem. Taking the specific case of TotalBalls=49 and NumberChosen=6.

  • Your choice of digits are 0 to (TotalBalls-1).
  • Base is TotalBalls.
  • Assume we index each position in the number from 0 to (NumberChosen-1)
  • Then the position 'multiplier' is \$Base^{positionIndex}\$. e.g. \$49^0, 49^1, ... , 49^5\$.
  • So if we iterate through each possible digit choice it can occur in each of the possible positions.
  • The count of numbers where a given digit occurs in a specific position will be the permutation of selecting (NumberChosen-1) from (TotalBalls-1). This basically fills the remaining positions from the remaining balls. In this instance it is \$P(48,5) = 205,476,480\$.
  • So the total of all numbers is: \$(0 + 1 + 2 + 3 + ... + (Base-1)) * P(Base-1, NumberChosen-1) \times ((Base-1)^0 + (Base-1)^1 + ... + (Base-1)^{NumberChosen-1})\$
  • Then take the total and divide by the count of the numbers which you can find as \$P\binom{Base}{NumberChosen}\$.

Calculation of the standard deviation

For this I suggest you use this identity the last one in that section. Basically find the sum of each number squared and subtract the expected value squared. Since you already know the latter, you're halfway there.

$$SD = \sqrt{\left({1\over N}\sum_{i=1}^N x^2\right) - \bar x^2}$$

This is slightly harder to calculate and I need to see how you can break apart the digits and treat them individually. If you can't do this, then you may as well take the naive approach of creating each number. I'll be back.

Suggestions

  • Create a method to calculate the permutation like Excel's function.
  • Consider whether your integers will overflow and whether you should use floating points and live with the loss of precision.
\$\endgroup\$
  • \$\begingroup\$ Code Review supports MathJax - there's an introduction here, and a larger tutorial here \$\endgroup\$ – rolfl Apr 9 '15 at 4:01
  • \$\begingroup\$ Note, I based my answer off the math in Lottery Math \$\endgroup\$ – rolfl Apr 9 '15 at 4:10
  • \$\begingroup\$ Trying to compress this in to a chat message: the different permutations don't make a difference to the mean/std-dev because the sums of the permutations are still the same, and the result would just be \$\frac{720 \times sums}{720 \times count}\$ \$\endgroup\$ – rolfl Apr 9 '15 at 4:28
  • \$\begingroup\$ Based on the chat session between @rolfl and I, I think I have the wrong idea of what the OP wanted. Also, I don't think its possible to determine the Std Dev by attacking each digit individually under my interpretation anyway! \$\endgroup\$ – Rossco Apr 9 '15 at 4:54
  • \$\begingroup\$ "Looking at the question, it seems to be a problem that is set for a university course, so I am reluctant to provide code directly". No i'm doing all this just for fun in hish school, you may or maynot provide any code. \$\endgroup\$ – RE60K Apr 9 '15 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.