random and unique subsets generation

Question

Lets say we have numbers from 1 to 25 and we have to choose sets of 15 numbers.

The possible sets are, if i'm right 3268760.

Of those 3268760 options, you have to generate say 100000

What would be the best way to generate 100000 unique and random of that subsets?

Is there a way, an algorithm to do that?

If not, what would be the best option to detect duplicates?

I'm planning to do this on PHP but a general solution would be enough, and any reference not to much 'academic' (more practical) would help me a lot.

Answer 1

There is a way to generate a sample of the subsets that is random, guaranteed not to have duplicates, uses O(1) storage, and can be re-generated at any time. First, write a function to generate a combination given its lexical index. Second, use a pseudorandom permutation of the first Combin(n, m) integers to step through those combinations in a random order. Simply feed the numbers 0...100000 into the permutation, use the output of the permutation as input to the combination generator, and process the resulting combination.