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