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

Другая возможность:

можно использовать массив флагов. И возьмите следующий когда это; s уже выбранный.

, Но, остерегайтесь после 1 000 вызовов функция никогда не будет заканчиваться так, необходимо сделать гарантию.

Вам даже не нужен массив для решения этого.

Вам нужны битовая маска и счетчик.

Инициализируют в противоречии с нулем и увеличивают его на последовательных вызовах. XOR счетчик с битовой маской (случайным образом выбранный при запуске или зафиксированный) для генерации psuedorandom числа. Если у Вас не может быть чисел, которые превышают 1000, не используйте битовую маску шире, чем 9 битов. (Другими словами, битовая маска является целым числом не выше 511.)

Удостоверяются, что, когда счетчик передает 1000, Вы обнуляете его. В это время можно выбрать другую случайную битовую маску — если Вам нравится — произвести тот же набор чисел в различном порядке.

Вы могли использовать Линейный Генератор Congruential . Где m (модуль) было бы самое близкое начало, больше, чем 1 000. Когда Вы вытаскиваете число из диапазона, просто получаете следующий. Последовательность только повторится, как только все элементы произошли, и Вы не должны использовать таблицу. Знайте о недостатках этого генератора хотя (включая отсутствие случайности).

Используйте Максимальный Линейный Сдвиговый регистр .

Обратной связи, Это реализуемо в нескольких строках C, и во времени выполнения делает немного больше чем пару теста/ответвлений, небольшого дополнения и разрядного смещения. Это не случайно, но это дурачит большинство людей.

Можно сделать это:

1. Создают список, 0.. 1000.
2. Перестановка список. (См. перестановка Фишера-Йетса для хорошего способа сделать это.)
3. числа Возврата в порядке от переставленного списка.

, Таким образом, это не требует поиска старых значений каждый раз, но он все еще требует O (N) для начальной перестановки. Но поскольку Nils указал в комментариях, это амортизируется O (1).

Вы могли использовать пользу генератор псевдослучайного числа с 10 битами и выбросить 1 001 - 1023 отъезда от 0 до 1 000.

От здесь мы получаем дизайн для PRNG на 10 битов..

• 10 битов, многочлен обратной связи x^10 + x^7 + 1 (период 1023)

• используют LFSR Galois для получения быстрого кода

Кто-то отправил "случайные числа создания в Excel". Я использую этот идеал. Создайте структуру с 2 частями, str.index и str.ran; Поскольку 10 случайных чисел создают массив 10 структур. Установите str.index от 0 до 9 и str.ran к другому случайному числу.

for(i=0;i<10; ++i) {
      arr[i].index = i;
      arr[i].ran   = rand();
}

Сортируют массив на значениях в прибытии [я] .ran. str.index находится теперь в произвольном порядке. Ниже код c:

#include <stdio.h>
#include <stdlib.h>

struct RanStr { int index; int ran;};
struct RanStr arr[10];

int sort_function(const void *a, const void *b);

int main(int argc, char *argv[])
{
   int cnt, i;

   //seed(125);

   for(i=0;i<10; ++i)
   {
      arr[i].ran   = rand();
      arr[i].index = i;
      printf("arr[%d] Initial Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   qsort( (void *)arr, 10, sizeof(arr[0]), sort_function);
   printf("\n===================\n");
   for(i=0;i<10; ++i)
   {
      printf("arr[%d] Random  Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   return 0;
}

int sort_function(const void *a, const void *b)
{
   struct RanStr *a1, *b1;

   a1=(struct RanStr *) a;
   b1=(struct RanStr *) b;

   return( a1->ran - b1->ran );
}

Для малых чисел, таких как 0 ... 1000, создание списка, содержащего все числа, и его перетасовка очень просто. Но если набор чисел для извлечения очень велик, есть еще один элегантный способ: вы можете построить псевдослучайную перестановку, используя ключ и криптографическую хеш-функцию. См. Следующий пример псевдокода C ++:

unsigned randperm(string key, unsigned bits, unsigned index) {
  unsigned half1 =  bits    / 2;
  unsigned half2 = (bits+1) / 2;
  unsigned mask1 = (1 << half1) - 1;
  unsigned mask2 = (1 << half2) - 1;
  for (int round=0; round<5; ++round) {
    unsigned temp = (index >> half1);
    temp = (temp << 4) + round;
    index ^= hash( key + "/" + int2str(temp) ) & mask1;
    index = ((index & mask2) << half1) | ((index >> half2) & mask1);
  }
  return index;
}

Здесь hash - это просто произвольная псевдослучайная функция, которая отображает строку символов в возможно огромное целое число без знака. Функция randperm представляет собой перестановку всех чисел в пределах 0 ... pow (2, bits) -1, предполагая фиксированный ключ. Это следует из конструкции, поскольку каждый шаг, изменяющий переменную index , является обратимым. Это навеяно шифром Фейстеля .

Вот код, который я набрал, использует логику первого решения. Я знаю, что это «независимо от языка», но просто хотел представить это в качестве примера на С# на случай, если кто-то ищет быстрое практическое решение.

// Initialize variables
Random RandomClass = new Random();
int RandArrayNum;
int MaxNumber = 10;
int LastNumInArray;
int PickedNumInArray;
int[] OrderedArray = new int[MaxNumber];      // Ordered Array - set
int[] ShuffledArray = new int[MaxNumber];     // Shuffled Array - not set

// Populate the Ordered Array
for (int i = 0; i < MaxNumber; i++)                  
{
    OrderedArray[i] = i;
    listBox1.Items.Add(OrderedArray[i]);
}

// Execute the Shuffle                
for (int i = MaxNumber - 1; i > 0; i--)
{
    RandArrayNum = RandomClass.Next(i + 1);         // Save random #
    ShuffledArray[i] = OrderedArray[RandArrayNum];  // Populting the array in reverse
    LastNumInArray = OrderedArray[i];               // Save Last Number in Test array
    PickedNumInArray = OrderedArray[RandArrayNum];  // Save Picked Random #
    OrderedArray[i] = PickedNumInArray;             // The number is now moved to the back end
    OrderedArray[RandArrayNum] = LastNumInArray;    // The picked number is moved into position
}

for (int i = 0; i < MaxNumber; i++)                  
{
    listBox2.Items.Add(ShuffledArray[i]);
}