Генератор случайных чисел

Решение: Генератор случайных чисел

Основная идея

Используем подход "Fisher-Yates shuffle" (также известный как "Knuth shuffle"):

1. Создаём слайс с числами от min до max
2. Тасуем (shuffle) случайно
3. Отправляем числа в канал
4. Закрываем канал

Простая реализация

import (
    "math/rand"
)

func UniqueRandomGenerator(min, max int) <-chan int {
    ch := make(chan int)
    
    go func() {
        defer close(ch)
        
        // Создаём слайс чисел [min, max]
        numbers := make([]int, max-min+1)
        for i := 0; i < len(numbers); i++ {
            numbers[i] = min + i
        }
        
        // Fisher-Yates shuffle
        for i := len(numbers) - 1; i > 0; i-- {
            j := rand.Intn(i + 1)
            numbers[i], numbers[j] = numbers[j], numbers[i]
        }
        
        // Отправляем числа в канал
        for _, num := range numbers {
            ch <- num
        }
    }()
    
    return ch
}

Как работает:

1. Горутина создаёт слайс: [min, min+1, ..., max]
2. Shuffle алгоритм: для каждого элемента с конца выбираем случайный элемент из оставшихся и меняем их местами
3. Отправляем перемешанные числа в канал
4. close(ch) сигнализирует завершение (цикл for range завершится)

Пример использования

func main() {
    gen := UniqueRandomGenerator(1, 10)
    for num := range gen {
        fmt.Println(num)
    }
}

Вывод (пример, порядок случайный):

7
2
9
1
5
8
3
10
4
6

Улучшенная версия с seed для предсказуемости

import (
    "math/rand"
    "time"
)

func UniqueRandomGenerator(min, max int) <-chan int {
    return UniqueRandomGeneratorWithSeed(min, max, time.Now().UnixNano())
}

func UniqueRandomGeneratorWithSeed(min, max int, seed int64) <-chan int {
    ch := make(chan int)
    
    go func() {
        defer close(ch)
        
        rng := rand.New(rand.NewSource(seed))
        
        numbers := make([]int, max-min+1)
        for i := 0; i < len(numbers); i++ {
            numbers[i] = min + i
        }
        
        // Fisher-Yates shuffle
        for i := len(numbers) - 1; i > 0; i-- {
            j := rng.Intn(i + 1)
            numbers[i], numbers[j] = numbers[j], numbers[i]
        }
        
        for _, num := range numbers {
            ch <- num
        }
    }()
    
    return ch
}

Преимущества:

• rand.New(rand.NewSource(seed)) создаёт локальный RNG
• Не конкурирует с глобальным random за мьютекс
• WithSeed вариант полезен для тестирования (воспроизводимые результаты)

Версия с буферизированным каналом (для контроля памяти)

func UniqueRandomGeneratorBuffered(min, max int, bufferSize int) <-chan int {
    ch := make(chan int, bufferSize)
    
    go func() {
        defer close(ch)
        
        numbers := make([]int, max-min+1)
        for i := 0; i < len(numbers); i++ {
            numbers[i] = min + i
        }
        
        rng := rand.New(rand.NewSource(time.Now().UnixNano()))
        for i := len(numbers) - 1; i > 0; i-- {
            j := rng.Intn(i + 1)
            numbers[i], numbers[j] = numbers[j], numbers[i]
        }
        
        for _, num := range numbers {
            ch <- num
        }
    }()
    
    return ch
}

Версия с math/rand/v2 (Go 1.22+)

import "math/rand/v2"

func UniqueRandomGenerator(min, max int) <-chan int {
    ch := make(chan int)
    
    go func() {
        defer close(ch)
        
        numbers := make([]int, max-min+1)
        for i := 0; i < len(numbers); i++ {
            numbers[i] = min + i
        }
        
        // Fisher-Yates shuffle с v2 API
        rand.Shuffle(len(numbers), func(i, j int) {
            numbers[i], numbers[j] = numbers[j], numbers[i]
        })
        
        for _, num := range numbers {
            ch <- num
        }
    }()
    
    return ch
}

Тестирование

func TestUniqueRandomGenerator(t *testing.T) {
    gen := UniqueRandomGeneratorWithSeed(1, 10, 42) // фиксированный seed
    
    seen := make(map[int]bool)
    count := 0
    
    for num := range gen {
        if num < 1 || num > 10 {
            t.Errorf("Number out of range: %d", num)
        }
        if seen[num] {
            t.Errorf("Duplicate number: %d", num)
        }
        seen[num] = true
        count++
    }
    
    if count != 10 {
        t.Errorf("Expected 10 numbers, got %d", count)
    }
}

Fisher-Yates алгоритм в деталях

Для массива [1, 2, 3, 4, 5]:

Шаг 1: i=4, j=random(0,4), например j=2
  Swap(5, 3) → [1, 2, 5, 4, 3]
  
Шаг 2: i=3, j=random(0,3), например j=1
  Swap(4, 2) → [1, 4, 5, 2, 3]
  
Шаг 3: i=2, j=random(0,2), например j=0
  Swap(5, 1) → [5, 4, 1, 2, 3]
  
Шаг 4: i=1, j=random(0,1), например j=0
  Swap(4, 5) → [4, 5, 1, 2, 3]
  
Результат: [4, 5, 1, 2, 3]

Сложность и производительность

• Время: O(n) для создания и shuffle
• Память: O(n) для хранения всех чисел
• Вероятность: каждая перестановка равновероятна (важно!)
• Горутина: работает асинхронно, не блокирует основной поток

Когда использовать

• Генерация лотерейных номеров
• Случайное распределение задач
• Перетасовка плейлиста
• Случайная выборка из набора

Это стандартный и эффективный способ генерировать уникальные случайные последовательности в Go.