Algorithm for calculating probabilities of a number being drawn opening a book

Question

I have a book with N<10000 pages, and a number x(in the range 1<=x<=40). I want to calculate the probability that, opening that book at random, the combination of the digits of the opened pages of the book are equals to the number.

The "level of combinations" may vary: from simple sum of digits (the event p.234 is true for x = 9), to combination of sums and subtractions up to pairs of digits[the event p.124 is true for x = 1, 2, 3(4-1), 4, 5(4+1), 6(2+4), 7(1+2+4), 8(12-4), 12, 14, 16(14+2), 23(24-1), 24, 25(24+1) ]

A starting note is that if you open a book, you'll always get page n and page n+1, so the probability should be calculated on the (2n-1,2n) couple, for each n, 1

Here what I'm doing

static protected int sommaCifreNumero(int numero){
    int retnum=0;
    for (char c : Integer.valueOf(numero).toString().toCharArray()){
        retnum += c - 48;
    }
    return retnum;
}

static public float calcolaProbabilitàSemplice(int da_interrogare, int ne_interroga)
{
    return (float)ne_interroga/(float)da_interrogare*100f;
}

/*
 * Questo sistema calcola le probabilità che aprendo un libro a caso, 
 * la somma delle cifre delle pagine diano il tuo numero nell'elenco del registro.
 * Se il tuo numero non può essere raggiunto, avrai sempre probabilità 0%.
 */

static public float calcolaProbabilitàLibroSemplice(int nPagine, int nRegistro)
{
    int maxNumberInterrogabile = 0;
    float retProb;
    maxNumberInterrogabile = sommaCifreNumero (nPagine);
    maxNumberInterrogabile = ((Integer.valueOf(nPagine).toString().length() == 2) && (Integer.valueOf(nPagine).toString().toCharArray()[1] -48 -1 + 9*1)>maxNumberInterrogabile) ? (Integer.valueOf(nPagine).toString().toCharArray()[1] -48 -1 + 9*1) : maxNumberInterrogabile;
    maxNumberInterrogabile = ((Integer.valueOf(nPagine).toString().length() == 3) && (Integer.valueOf(nPagine).toString().toCharArray()[2] -48 -1 + 9*2)>maxNumberInterrogabile) ? (Integer.valueOf(nPagine).toString().toCharArray()[1] -48 -1 + 9*2) : maxNumberInterrogabile;
    maxNumberInterrogabile = ((Integer.valueOf(nPagine).toString().length() == 4) && (Integer.valueOf(nPagine).toString().toCharArray()[3] -48 -1 + 9*3)>maxNumberInterrogabile) ? (Integer.valueOf(nPagine).toString().toCharArray()[1] -48 -1 + 9*3) : maxNumberInterrogabile;

    if(nRegistro>maxNumberInterrogabile)
    {
        retProb = 0.f;
        return 0.f;
    }//il numero massimo raggiungibile è inferiore al numero in registro -> non puoi essere chiamato
    int favorevoli = 0;
    for(int i=1; i<=nPagine; i++)
    {
        if(sommaCifreNumero(i)==nRegistro || i==nRegistro)
            favorevoli++;
    }

    retProb = (float) favorevoli / (float) nPagine * 100f;
    return retProb;
}

/*
 * Questo sistema è un'estensione del precedente: somma le cifre 
 * di una pagina aperta a caso, ma anche a coppie(es: p.124 può dare 12, 16, 24, 25).
 */

static public float calcolaProbabilitàLibroComplessa(int nPagine, int nRegistro)
{
    String pagstring;
    float retProb;
    int nRegLength = String.valueOf(nRegistro).length();
    int favorevoli = 0;
    int totali = 0;
    Vector<Integer> possibili;
    int number_to_add;
    int number_added;
    for(int i = 1;i<=nPagine; i++)
    {
        possibili = new Vector<Integer>();
        pagstring = Integer.valueOf(i).toString();
        for(int a=0; a+nRegLength<=pagstring.length(); a++)
        {
            String numero_selezionato = pagstring.substring(a,a+nRegLength);

            if (Integer.parseInt(numero_selezionato)<=31)  possibili.add(Integer.parseInt(numero_selezionato));
            //somma le parti prima
            for(int b=0; b<a; b++)
            {//b è l'indice iniziale della sottostringa che verrà sommata
                for(int c=1; c<=nRegLength; c++)
                {//c è l'indice +1 finale della sottostringa che verrà sommata
                    if(b+c<=a)
                    {
                        number_to_add = Integer.parseInt(pagstring.substring(b,b+c));
                        if (number_to_add!=0)
                        {
                            number_added = Integer.parseInt(numero_selezionato) + number_to_add;
                            if (number_added <31) possibili.add(number_added);
                        }
                    }
                }
            }
            //somma le parti dopo
            for(int b=a+nRegLength; b<pagstring.length(); b++)
            {
                for(int c=1; c<=nRegLength; c++)
                {
                    if(b+c<=pagstring.length())
                    {
                        number_to_add = Integer.parseInt(pagstring.substring(b,b+c));
                        if (number_to_add!=0)
                        {
                            number_added = Integer.parseInt(numero_selezionato) + number_to_add;
                            if (number_added <31) possibili.add(number_added);
                        }
                    }
                }
            }
            totali += possibili.size();
            for(int numero: possibili) favorevoli+= numero==nRegistro ? 1:0;

        }
    }
    retProb = (float)favorevoli/(float)totali * 100f;
    return retProb;
}

The first method calculates the sum of the digits of a number, the second the probability that the opened page number are equal to the x, or their digits sum is. The third check also couples of digits.

1) I'm not taking in count the note I made before.

2) I'll run this on a mobile device.

3) Right now I really feel the results are wrong.

I was wondering if a table of precalculated results would fit better. I know that N is < 10000, so I can use an array[40][10000] for storing the results to load at runtime, but I'm not to keen in file manipulations in Java, in addition I'll need to store this for, say, 4 different methods of calculating the probability, so, how much memory would it consume? And is it a problem to calculate this at runtime instead? Is there a better approach(or maybe an already written algorithm) for doing this?

Answer 1

Calculate the number of sums you'll have from 1 <= page # <= N, where N is the number of pages. It's far less than 10,000, because 1 and 10 and 100 and 1000 and 10000 all map to the sum 1. The max value you'll have comes from 9999 => 36. You can start with a map where the page # is the key and the sum is the value, then reverse it and have map where sum is the key and a list of pages whose numbers sum is equal to the key is the value.

For 10,000 pages, all possible sums fall between 1 and 36.

So if you choose a random number from some range, use that as the key into the reversed map to get the list of pages that map to that sum. The length of that list divided by the number of pages is the probability you want.

Here's how I'd do it:

package misc;

import java.util.*;

/**
 * PageSumProbability
 *
 * @author Michael
 * @since 10/14/11
 */
public class PageSumProbability {

    private Map<Integer, Integer> pageNumberSum;
    private Map<Integer, List<Integer>> sumPageNumbers;

    public static void main(String[] args) {
        if (args.length > 1) {
            int maxPageNumber = Integer.valueOf(args[0]);            
            int randomSum = Integer.valueOf(args[1]);
            PageSumProbability psp = new PageSumProbability(maxPageNumber);
            System.out.println(psp.getPageNumberSum());
            System.out.println(psp.getSumPageNumbers());
            System.out.printf("random sum: %d probability of opening page # that equals random sum: %5.3f%%\n",
                    randomSum, 100*psp.getProbabilityOfSum(randomSum));
        } else {
            System.out.print("Usage: PageProbabilitySum <# pages> <random sum>");
        }
    }

    public PageSumProbability(int maxPageNumber) {
        this.pageNumberSum = new TreeMap<Integer, Integer>();
        this.sumPageNumbers = new TreeMap<Integer, List<Integer>>();

        for (int i = 1; i <= maxPageNumber; ++i) {
            int sum = this.calculateSumOfDigits(i);
            this.pageNumberSum.put(i, sum);
            List<Integer> pages = this.sumPageNumbers.get(sum);
            if (pages == null) {
                pages = new LinkedList<Integer>();
            }
            pages.add(i);
            this.sumPageNumbers.put(sum, pages);
        }
    }

    public static int calculateSumOfDigits(int pageNumber) {
        int sum = 0;
        String pageNumberAsString = String.valueOf(Math.abs(pageNumber));
        for (int i = 0; i < pageNumberAsString.length(); ++i) {
            StringBuilder digit = new StringBuilder();
            digit.append(pageNumberAsString.charAt(i));
            sum += Integer.valueOf(digit.toString());
        }

        return sum;
    }

    public double getProbabilityOfSum(int randomSum) {
        if (randomSum <= 0)
            throw new IllegalArgumentException("random sum must be greater than zero");
        double probability = 0.0;
        List<Integer> pages = this.sumPageNumbers.get(randomSum);
        if (pages != null) {
            probability = (double) pages.size()/this.pageNumberSum.size();
        }

        return probability;
    }

    public Map<Integer, Integer> getPageNumberSum() {
        return Collections.unmodifiableMap(this.pageNumberSum);
    }

    public Map<Integer, List<Integer>> getSumPageNumbers() {
        return Collections.unmodifiableMap(this.sumPageNumbers);
    }
}