Уникальные (неповторяющиеся) случайные числа в O (1)?

Question

Я хотел бы генерировать уникальные случайные числа от 0 до 1000, которые никогда не повторяются (то есть 6 не появляется дважды), но это не прибегает к чему-то вроде поиска O (N) предыдущих значений, чтобы сделать Это. Возможно ли это?

Answer 1

Фишер Йейтс

for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Это на самом деле O (n-1), так как вам нужен только один своп для последних двух
Это C #

public static List<int> FisherYates(int n)
{
    List<int> list = new List<int>(Enumerable.Range(0, n));
    Random rand = new Random();
    int swap;
    int temp;
    for (int i = n - 1; i > 0; i--)
    {
        swap = rand.Next(i + 1);  //.net rand is not inclusive
        if(swap != i)  // it can stay in place - if you force a move it is not a uniform shuffle
        {
            temp = list[i];
            list[i] = list[swap];
            list[swap] = temp;
        }
    }
    return list;
}