language: Java (sun-jdk-1.7.0_10)
date: 272 days 14 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import java.math.BigInteger;
import java.util.LinkedHashMap;
 
class CountStrings2 {
 
        // cache. key: N:M
        private LinkedHashMap<String, BigInteger> sNM = new LinkedHashMap<String, BigInteger>();
        private final int P;
 
        public CountStrings2(int P, int N, int M) {
                this.P = P;
                BigInteger S = computeS(N, M);
                System.out.println("P=" + P + " N=" + N + " M=" + M + " S=" + S);
                //outputCaches();
                computeAsympt(N,M);
        }
 
        private BigInteger computeS(int N, int M) {
                String k = N + ":" + M;
                if (!sNM.containsKey(k)) {
                        BigInteger b = BigInteger.ZERO;
                        if (N < M) {
                                b = BigInteger.valueOf(P).pow(N);
                        } else {
                                for (int i= 1; i < M; i++) {
                                        b = b.add(computeS(N-i, M));
                                }
                                b = b.multiply(BigInteger.valueOf(P-1));
                        }
                        sNM.put(k, b);
                }
 
                return sNM.get(k);
        }
 
        public void outputCaches() {
                System.out.println("============== SNM ====  (P=" + P + ")");
                for (String k : sNM.keySet()) {
                        System.out.println("SNML " + k + "=" + sNM.get(k));
                }
        }
 
        public void computeAsympt(int N, int M) { // asympotic approximation 
                double theta = 1.0 / P;
                double probasympt =  Math.pow(1 - Math.pow(theta, M - 1),N * (1 - theta));
                BigInteger S = computeS(N, M);
                BigInteger cc = BigInteger.valueOf(P).pow(N).multiply(BigInteger.valueOf(1000000)).divide(S);
                double probexact = 1000000.0/cc.doubleValue();
                System.out.printf("prob:%.4f asymptotic:%.4f\n" ,probexact, probasympt);
        }
 
        public static void main(String[] args) {
                new CountStrings2(4, 50, 5);
 
        }
}