How to Generate Unique Full Names from $names[], $surnames[]?

I have two arrays (actual size is 10x bigger):

$names = array(
    'James',
    'John',
    'Robert',
    'Michael',
    'William'
);

$surnames = array(
    'Smith',
    'Johnson',
    'Williams'
);

I need to generate people's full names. One person can only have one name and one surname. Full names must be unique! What's the best solution?

P.S. I don't need all possible names. I think that when there can't be made any other unique full names from given arrays... I will throw an exception!

Solution #1:

The first one that came in my mind...

Create new array called full_names and store generated names in there. Before storing, check that there aren't such value already. Generate by random.

This gonna be so开发者_如何学C slow! And stupid.

Solution #2:

Ask on StackOverflow.com algorithm for generating all possible full names... and then take only that much as I need. No, this sounds stupid as well...

Make an array of (i,j) integer doublets covering all possible name-surname combinations. Shuffle the array. Then just loop through the array, and take names from it one by one.

You'll get unique full names in random order (provided that your name and surname lists don't contain duplicates).

EDIT

Pseudocode, per request.

First, do these setup steps:

indexList = emptyList
for i = 1 to length(first_names)
  for j = 1 to length(last_names)
    indexList.push( (i,j) )

shuffle(indexList)

push here means adding an element to the end of the list.

Now every time you need a new name, just take one index pair off indexList, and return the corresponding names from the name arrays:

function getName()
  (i, j) = indexList.pop()
  return concatenate(first_names[i], " ", last_names[j])

pop here means remove an element from the end of the list and return it. It is unlikely that you'd have so many names that the indexList should take up too much memory.

Loop over the first and last names, check if you already generated that combination. In PHP:

$full_names = array();
foreach ($names as $first_name) {
    foreach ($surnames as $last_name) {
        $candidate = $first_name . " " . $last_name;
        if (!isset($full_names[$candidate])) {
            $full_names[$candidate] = true;
        }
    }
}

print_r(array_keys($full_names));

Or same in Python:

print set([first + ' ' + last for first in names for last in surnames])