The algorithm for calculating the probabilities of the number that opens opens the 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 when opening this book at random, the combination of the numbers of the open pages of the book is equal to the number.

The “combination level” can vary: from a simple sum of digits (event p.234 is true for x = 9), combinations of sums and subtractions to pairs of digits [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)]

The initial note is that if you open the book, you always get page n and page n + 1, so the probability should be calculated for a pair (2n-1,2n) for each n, 1

That's 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 the number, the second - the probability that the number of the open page is x, or the sum of their digits. The third check is also a pair of numbers.

1) I do not take into account the note that I made earlier.

2) I ran this on a mobile device.

3) Now I really feel that the results are wrong.

I was wondering if the table of pre-calculated results would fit better. I know that N is <10000, so I can use the array [40] [10000] to store the results for loading at runtime, but I will not get involved in file manipulation in Java, in addition, I will need to save this, say, 4 different methods for calculating probability, so how much memory will it consume? And is it a problem to calculate this at runtime instead? Is there a better way (or perhaps an already written algorithm) for this?

Answer 1

Calculate the number of sums you get from 1 <= page # <= N, where N is the number of pages. This is much less than 10,000, because 1 and 10 and 100 and 1000 and 10000 are all matched with sum 1. The maximum value you get is from 9999 => 36. You can start with a map where page # is the key and the sum - this is the value, then turn it over and point the map, where the sum is the key, and the list of pages whose number is equal to the number is equal to the value.

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

So, if you select a random number from a certain range, use it as a key in the reverse card to get a list of pages that are mapped to this amount. The length of this list divided by the number of pages is the probability you want.

Here is how I would 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); } } 

Answer 2

Here is how I would do it.

Define the DigitCombinationStragtegy interface with one method: Set<Integer> combineDigits(int pageNumber) .

Write an implementation of this interface for each method of combining numbers: SumDigitCombinationStragtegy, SubstractionDigitCombinationStragtegy, etc. Each strategy returns a set of combinations that it generates. This is actually the hardest part of the problem. But implementing only the smallest details is easier than anything, and you can easily unit test each strategy.

Write an implementation of this strategy that simply takes a set of other strategies and combines all the return factors.

When querying the book and the number N, initialize two numbers to 0: hits and misses . Follow the appropriate strategy. Iterate over pages (or pairs of pages) and set strategies for the set of numbers that it generates. for this page (or this page pair). If the set contains N, the increment increases. Else, increased misses.

Probability is hits / (hits + misses).