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

Решение

Анализ задачи

Требования:

• Генерировать n уникальных случайных чисел в диапазоне [min, max]
• Если невозможно выбрать n уникальных чисел, вернуть ошибку
• Обрабатывать граничные случаи

Сложность: нужно избежать бесконечного цикла, если n больше количества доступных чисел.

Решение 1: Использование map для отслеживания

func generateUniqueSlice(n, min, max int) ([]int, error) {
    // Проверка валидности
    if n < 0 || min > max {
        return nil, errors.New("invalid parameters")
    }
    
    // Количество доступных чисел
    available := max - min + 1
    if n > available {
        return nil, fmt.Errorf("cannot generate %d unique numbers in range [%d, %d]", n, min, max)
    }
    
    // Используем map для отслеживания уже выбранных чисел
    used := make(map[int]bool)
    result := make([]int, 0, n)
    
    // Генерируем случайные числа
    for len(result) < n {
        randomNum := rand.Intn(max-min+1) + min
        if !used[randomNum] {
            used[randomNum] = true
            result = append(result, randomNum)
        }
    }
    
    return result, nil
}

Плюсы:

• Простая логика
• O(n) в среднем случае

Минусы:

• При n близком к (max - min + 1) может быть медленным из-за большого количества коллизий

Решение 2: Метод перемешивания (Fisher-Yates)

func generateUniqueSlice(n, min, max int) ([]int, error) {
    // Проверка валидности
    if n < 0 || min > max {
        return nil, errors.New("invalid parameters")
    }
    
    available := max - min + 1
    if n > available {
        return nil, fmt.Errorf("cannot generate %d unique numbers in range [%d, %d]", n, min, max)
    }
    
    // Создаём слайс со всеми числами в диапазоне
    nums := make([]int, available)
    for i := 0; i < available; i++ {
        nums[i] = min + i
    }
    
    // Перемешиваем с помощью Fisher-Yates shuffle
    for i := len(nums) - 1; i > 0; i-- {
        j := rand.Intn(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    }
    
    // Возвращаем первые n элементов
    return nums[:n], nil
}

Плюсы:

• O(max - min) один раз, затем O(n) для выбора
• Гарантированно даст результат за одинаковое время
• Все числа имеют равную вероятность

Минусы:

• Требует больше памяти для промежуточного слайса

Решение 3: Оптимизированное (гибридное)

func generateUniqueSlice(n, min, max int) ([]int, error) {
    if n < 0 || min > max {
        return nil, errors.New("invalid parameters")
    }
    
    available := max - min + 1
    if n > available {
        return nil, fmt.Errorf("cannot generate %d unique numbers in range [%d, %d]", n, min, max)
    }
    
    // Если нужно генерировать больше половины диапазона, используем Fisher-Yates
    if n > available/2 {
        nums := make([]int, available)
        for i := 0; i < available; i++ {
            nums[i] = min + i
        }
        
        for i := len(nums) - 1; i > 0; i-- {
            j := rand.Intn(i + 1)
            nums[i], nums[j] = nums[j], nums[i]
        }
        
        return nums[:n], nil
    }
    
    // Иначе используем set
    used := make(map[int]bool)
    result := make([]int, 0, n)
    
    for len(result) < n {
        randomNum := rand.Intn(available) + min
        if !used[randomNum] {
            used[randomNum] = true
            result = append(result, randomNum)
        }
    }
    
    return result, nil
}

Полный пример с инициализацией seed

package main

import (
    "errors"
    "fmt"
    "math/rand"
    "time"
)

func generateUniqueSlice(n, min, max int) ([]int, error) {
    if n < 0 || min > max {
        return nil, errors.New("invalid parameters")
    }
    
    available := max - min + 1
    if n > available {
        return nil, fmt.Errorf("cannot generate %d unique numbers in range [%d, %d]", n, min, max)
    }
    
    if n > available/2 {
        nums := make([]int, available)
        for i := 0; i < available; i++ {
            nums[i] = min + i
        }
        
        for i := len(nums) - 1; i > 0; i-- {
            j := rand.Intn(i + 1)
            nums[i], nums[j] = nums[j], nums[i]
        }
        
        return nums[:n], nil
    }
    
    used := make(map[int]bool)
    result := make([]int, 0, n)
    
    for len(result) < n {
        randomNum := rand.Intn(available) + min
        if !used[randomNum] {
            used[randomNum] = true
            result = append(result, randomNum)
        }
    }
    
    return result, nil
}

func main() {
    rand.Seed(time.Now().UnixNano())
    
    nums, err := generateUniqueSlice(5, 1, 10)
    if err != nil {
        fmt.Println("Error:", err)
    } else {
        fmt.Println("Generated:", nums)
    }
    
    // Ошибка
    nums, err = generateUniqueSlice(15, 1, 10)
    if err != nil {
        fmt.Println("Error:", err)
    }
}

Рекомендация

Используй гибридный подход — он оптимален для всех случаев: быстрый для малых n и гарантированно завершающийся для больших n.