Как эффективно выбрать случайное количество комбинаций из всех комбинаций

Question

Например, у меня есть два массива (первый массив содержит первые имена, а второй массив фамилии).Я хочу сгенерировать n чисел уникальных неповторяющихся комбинаций из этих двух массивов с таким порядком >>> first_name + '' + last_name.

Я не хочу создавать каждую возможную комбинацию заранее, потому что этослишком много памяти.

Так что я думаю, что алгоритм должен делать, это повторять до тех пор, пока комбинации не будут сгенерированы, во время итерации он должен дать некоторые случайные индексы для обоих массивов, и если эти индексы уже используются вместеПопробуйте выбрать другое случайное число, пока уникальные индексы не будут сгенерированы.Но этот подход может вызвать глубокую рекурсию во время выполнения, так как столько выходов уже дано, вероятность того, что новые случайные индексы будут сопоставлены с существующими, будет возрастать на каждом шаге.

Так что вы, ребята, советуете,как я могу выбрать случайные, уникальные n элементов из несуществующих / виртуальных 2 комбинаций элементов массива с очень оптимизированным способом

Answer 1

Если у вас F уникальных имен и L уникальных фамилий, то общее число комбинаций равно N = F * L

Таким образом, вы можете сгенерировать необходимое количество неповторяющихся случайных целых значений в диапазоне 0..N-1 (например, с помощью выборки Фишера-Йейтса), отсортируйте их и получите соответствующие комбинации имен:

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]