Получить набор из n уникальных случайных чисел

Условие

Необходимо написать функцию uniqRandn(n int) []int, которая вернёт массив из ровно n различных случайных целых чисел. При каждом запуске программы набор чисел должен быть случайным, но внутри результата не должно быть дубликатов.

import (
 "fmt"
 "math/rand"
)

func main() {
 fmt.Println(uniqRandn(10))
}

func uniqRandn(n int) []int {
 // ...
}

Функция должна корректно работать при любых значениях n (в разумных пределах), гарантируя уникальность всех элементов возвращаемого среза.

Ответ

Выборка без возвращения даёт n уникальных чисел за O(n), без повторных попыток при коллизиях. Отрицательное n нужно явно отклонять.

Алгоритм Флойда для диапазона [0, MaxInt):

func uniqRandn(n int) []int {
    if n < 0 { panic("n must be non-negative") }
    limit := int(^uint(0) >> 1)
    used := make(map[int]struct{}, n)
    result := make([]int, 0, n)
    for j := limit-n; j < limit; j++ {
        value := rand.Intn(j + 1)
        if _, exists := used[value]; exists { value = j }
        used[value] = struct{}{}
        result = append(result, value)
    }
    return result
}

Нужен math/rand. На шаге j прежние значения меньше j: если случайное число занято, сам j свободен. Память O(n); разумные n ограничены памятью. Случайность не гарантирует различия результатов разных запусков и не подходит для секретов.