fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. /* Name of the class has to be "Main" only if the class is public. */
  6. class Balls 
  7. {
  8.  
  9. 	// not necessarily normalized
  10.     final static double prob[] = { 0.3, 0.2, 0.2, 0.15, 0.1, 0.05 };
  11.     final static int N = prob.length;
  12.  
  13. 	public static void main (String[] args) throws java.lang.Exception	{
  14. 		int j=2; // which element? (0..N-1)
  15. 		normalize(prob);
  16. 		System.out.println("prob=" + Arrays.toString(prob));
  17. 		for(int t=0;t<=N;t++) {
  18. 			double p=computeProb(j,t);
  19. 			System.out.printf("j=%d t=%d p=%.6f\n",j,t,p);
  20. 		}
  21. 	}
  22.  
  23.     /**
  24.      * Computes probabiity that element j (j=0..N-1, same index as in prob array)
  25.      * does not appear in the first pos positions
  26.  
  27.      * computeProb(element, 0) = 1
  28.      * computeProb(element, 1) = 1-p_j 
  29.      * computeProb(element, N) = 0 
  30.      */
  31.     public static double computeProb(int j, int pos) {
  32.         normalize(prob);
  33.         double[] p0 = removeAndNormalize(prob, j, false);
  34.         return allPermutations(p0, pos);
  35.     }
  36.  
  37.     static double allPermutations(double p[], int depth) {
  38.         double ac = 0;
  39.         if( depth <= 0 ) return 1;
  40.         for( int i = 0; i < p.length; i++ ) 
  41.             ac += p[i] * allPermutations(removeAndNormalize(p, i, true), depth - 1);
  42.         return ac;
  43.     }
  44.  
  45.     // normalizes probabities in place
  46.     static void normalize(double[] list) {
  47.         double ac = 0;
  48.         for( double px : list )         ac += px;
  49.         for( int i = 0; i < list.length; i++ )          list[i] /= ac;
  50.     }
  51.  
  52.     // removes element of array, and optionally normalizes 
  53.     // original (untouched) must be already normalized 
  54.     static double[] removeAndNormalize(double p[], int index, boolean normalize) {
  55.         double[] q = new double[p.length - 1];
  56.         for( int i = 0, j = 0; i < q.length; i++, j++ ) {
  57.             if( i == index ) j++;
  58.             q[i] = normalize ? p[j] / (1 - p[index]) : p[j];
  59.         }
  60.         return q;
  61.     }
  62.  
  63.  
  64. }
Success #stdin #stdout 0.12s 320512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
prob=[0.3, 0.2, 0.2, 0.15, 0.1, 0.05]
j=2 t=0 p=1.000000
j=2 t=1 p=0.800000
j=2 t=2 p=0.596243
j=2 t=3 p=0.394575
j=2 t=4 p=0.207791
j=2 t=5 p=0.063296
j=2 t=6 p=0.000000
https://ideone.com/g52KgY
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!