Search code examples
javascriptarraysrandomuniquecombinations

How to randomly pick a number of combinations from all the combinations efficiently

For example I have two array (first array contains first names and second array last names). I want to generate n number of unique, non-repeating combinations from this two arrays with such ordering >>> first_name + ' ' + last_name.

I don't wish to generate every possible combination beforehand, because it's too much memory-consuming.

So what I think that algorithm should do, is to iterate until combinations are not generated, during iteration, it should give some random indexes for both arrays and if those indexes are already used together try to pick another random numbers until unique indexes are not generated. But this approach might trigger deep recursion during runtime, since as many outputs are already given, a chance that new random indexes will be matched with existing ones is going higher at each step.

So what is your suggestion guys, how can I select random, unique n items from non-existing/virtual 2 array element combinations with very optimized way

Solution

  • If you have F unique first names and L unique last names, then overall number of combinations is N = F * L

    So you can generate needed number of non-repeating random integer values in range 0..N-1 (for example, with Fisher-Yates sampling), sort them, and get corresponding name combinations:

    for i = 0..M-1
    Generate K[i] = Random(N)
Sort K[]
for i = 0..M-1
   FirstNameIndex = K[i] / L    //integer division
   LastNameIndex = K[i] % L     //integer modulo
   Combination[i] = First[FirstNameIndex] + Last[LastNameIndex]