I need to manipulate massive numbers and large sets in Java. I prefer Java as it is what I am familiar with, but if this problem is best suited for another language that might be ok.
Basically I am trying to answer the following question:
Suppose you choose p sets of n numbers from 1 to x. If k numbers are drawn from 1 to x (k > n), what is the minimum value of p such that out of any k set you have at least on p set that matches?
I cannot find an easy way to calculate the value of p. Some of my thoughts as well as others can be found on this forum:
[url removed, login to view]~wwu/cgi-bin/yabb/[url removed, login to view];action=display;num=1297051711
Since P cannot be easily found, I wish to create a java program to find p for me. As well as finding p it should be able to list the sets of numbers. I have already created a Java program to list all the possible combinations of x items taken k at a time and output them to a text file xCk.txt. This program can be found in the attached files. It took about 5 hours to generate all the combinations up to 24x24, which produces 300 text files totaling 1.3GB. This program may or may not be helpful. And here is a link to those files:
[url removed, login to view]
As an example I took the values of x=6 k=3 and n=2 and asked what the minimum p would be. In this case it is 6, meaning I need at most 6 sets of 2 numbers from 1 to 6 to guarantee a match with any given 3 numbers pulled.
There are a total of 15 different ways to pull 2 numbers from 6. And there is a total of 5,005 ways to arrange the 15 sets of 2 into groups of 6. Out of those 5005 groups of 6 only 10 groups satisfy the conditions needed.
As you can see dealing with even small numbers in this case 6,3 and 2, requires large sets of numbers.
The program should go through all permutations of x, k, and n, up to 100,100,100. The program needs to find the lowest value of p. the program needs to list the numbers in the set for p.
I do realize that this require a lot of computing power to run, so the program should be optimized for 64bit processors and it should utilize multithreading to take advantage of multi-core processor abilities. It does have to be quick but I do understand that running such a program to completion will take weeks or even months, as it is just a brute force program.
The end goal is to have a the numbers to look at for further reasearch.