jpayne@68: package fun;
jpayne@68: 
jpayne@68: import java.util.HashSet;
jpayne@68: import java.util.Random;
jpayne@68: 
jpayne@68: public class ProbShared3 {
jpayne@68: 
jpayne@68: 	public static void main(String args[]){
jpayne@68: 		int k=Integer.parseInt(args[0]);
jpayne@68: 		int len1=Integer.parseInt(args[1]);
jpayne@68: 		int len2=Integer.parseInt(args[2]);
jpayne@68: 		int rounds=Integer.parseInt(args[3]);
jpayne@68: 		
jpayne@68: 		System.out.println("Probability:   "+simulate(k, len1, len2, rounds));
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	static double simulate(int k, int len1, int len2, int rounds){
jpayne@68: 		int successes=0;
jpayne@68: 		final HashSet<Long> set=new HashSet<Long>();
jpayne@68: 		for(int i=0; i<rounds; i++){
jpayne@68: 			successes+=simulateOnePair(k, len1, len2, set);
jpayne@68: 		}
jpayne@68: 		return successes/(double)rounds;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	static int simulateOnePair(int k, int len1, int len2, HashSet<Long> set){
jpayne@68: 		fillRandomSet(k, len2, set);
jpayne@68: 		final long space=(long)Math.pow(4, k);
jpayne@68: 		final int kmers=len1-k+1;
jpayne@68: 		for(int i=0; i<kmers; i++){
jpayne@68: 			long kmer=(randy.nextLong()&Long.MAX_VALUE)%space;
jpayne@68: 			if(set.contains(kmer)){return 1;}
jpayne@68: 		}
jpayne@68: 		return 0;
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	static void fillRandomSet(int k, int len, HashSet<Long> set){
jpayne@68: 		set.clear();
jpayne@68: 		final long space=(long)Math.pow(4, k);
jpayne@68: 		final int kmers=len-k+1;
jpayne@68: 		for(int i=0; i<kmers; i++){
jpayne@68: 			set.add((randy.nextLong()&Long.MAX_VALUE)%space);
jpayne@68: 		}
jpayne@68: 	}
jpayne@68: 	
jpayne@68: 	static final Random randy=new Random();
jpayne@68: 	
jpayne@68: }