Как реализовать генерацию списка уникальных случайных чисел без использования встроенных функций типа sample?

Генерация уникальных случайных чисел

Когда требуется получить список неповторяющихся случайных чисел, часто прибегают к встроенным функциям, таким как random.sample в Python. Однако понимание того, как реализовать это вручную, демонстрирует глубокое знание алгоритмов и структур данных.

Алгоритм перемешивания Фишера-Йетса

Один из самых эффективных способов — это алгоритм перемешивания Фишера-Йетса (также известный как алгоритм Кнута). Он работает за O(n) времени и O(n) памяти. Идея заключается в том, чтобы создать массив всех возможных чисел в заданном диапазоне, а затем случайным образом перемешать его. После этого первые k элементов перемешанного массива будут представлять собой k уникальных случайных чисел.

Пример реализации на Python

import random

def unique_random_numbers(count, min_val, max_val):
    if count > (max_val - min_val + 1):
        raise ValueError("Count exceeds range size")
    
    # Создаем массив всех чисел в диапазоне
    numbers = list(range(min_val, max_val + 1))
    
    # Перемешиваем массив с помощью алгоритма Фишера-Йетса
    for i in range(len(numbers) - 1, 0, -1):
        j = random.randint(0, i)
        numbers[i], numbers[j] = numbers[j], numbers[i]
    
    # Возвращаем первые count элементов
    return numbers[:count]

# Пример использования
print(unique_random_numbers(5, 1, 10))

Альтернативный подход с использованием множества

Другой подход — использовать множество для отслеживания уже выбранных чисел. Генерируем случайное число, проверяем, есть ли оно в множестве, и если нет — добавляем. Этот метод менее эффективен при большом количестве чисел, так как может потребоваться много попыток, особенно когда количество запрашиваемых чисел близко к размеру диапазона.

def unique_random_numbers_set(count, min_val, max_val):
    if count > (max_val - min_val + 1):
        raise ValueError("Count exceeds range size")
    
    result = set()
    while len(result) < count:
        num = random.randint(min_val, max_val)
        result.add(num)
    return list(result)

Вывод

Алгоритм Фишера-Йетса предпочтителен, когда требуется гарантированная производительность и равномерное распределение. Подход с множеством проще в реализации, но может быть медленнее при большом количестве чисел. Выбор метода зависит от конкретных требований к производительности и размеру данных.