Псевдослучайная последовательность без повторов элементов.

[TorBel]

Псевдослучайная последовательность без повторов элементов.


Иногда возникает необходимость получить псевдослучайную последовательность без повторов получаемых элементов.
Предлагаю Вашему вниманию один из простых способов получения необходимого результата, которым я пользуюсь много лет. Хочу сразу сказать, что его я нашёл в одной из книг по программированию(за давностью лет, уже не помню в какой) и на авторство не претендую.
Пример будет написан на языке программирования Pascal, но перевести его на другой язык программирования, я думаю, не составит большого труда. В примере мы получим последовательность целых положительных чисел, но применять способ можно для любых типов данных. Итак, приступим.
Зададим количество получаемых чисел. Пусть мы хотим получить 10 чисел из диапазона 1..10.

 const
  NumCount=10;

Теперь определим рабочий массив и переменные, используемые в программе.

 var
  RandAr: array[1..NumCount] of Cardinal;
  i, j, n: Cardinal;

Конечно, в качестве типа значений массива в конкретном случае можно было использовать и тип Byte для экономии памяти, но для универсальности воспользуемся нативным типом Cardinal(да и для скорости будет полезно). Это же замечание можно применить и к типу переменных.
Теперь проинициализируем массив.

  for i:=1 to NumCount do
   RandAr[i]:=i;

Мы заполнили массив арифметической последовательностью чисел в заданном диапазоне.
А теперь перемешаем массив чисел в псевдослучайном порядке.

  Randomize;
  for i:=1 to (NumCount-1) do
   begin
    j:=Random(NumCount-i+1)+i;
    n:=RandAr[i];
    RandAr[i]:=RandAr[j];
    RandAr[j]:=n;
   end;

После этого в рабочем массиве RandAr расположена неповторяющееся псевдослучайная последовательность из заданных чисел.

Несколько замечаний.
1. В примере использован статический массив, но современные диалекты языка позволяют использовать и динамический массив, что оказывается очень удобно, когда число элементов заранее неизвестно и определяется в ходе выполнения программы.
2. Если Вам нужна последовательность начинающееся с 0, то вместо

  for i:=1 to NumCount do
   RandAr[i]:=i;

следует написать

  for i:=1 to NumCount do
   RandAr[i]:=i-1;

Тогда у Вас будет массив, заполненный числами от 0 до NumCount-1.
Само собой разумеется, что массив можно заполнить любыми числами, псевдослучайную последовательность которых Вы хотите получить на выходе. Для этого, например, можно инициализировать массив в тексте программы или прочитать числа с любого устройства ввода.
3. Можно создать массив любого типа и, перемешав его, получить, соответственно, псевдослучайную последовательность любых данных. Однако для этого можно применить более эффективный, в некоторых случаях, способ, описанный ниже.
4. В некоторых случаях перемешивание можно ускорить, проверяя соотношение переменных i и j и, в случае их равенства пропускать перестановку. Это может оказаться выгодно в случае применения замечания номер 3.
5. Если элементы данных имеют размер больше Cardinal(например, строки), то, на мой взгляд, будет выгоднее с точки скорости работы программы создать дополнительный массив или список из этих элементов, а полученную в рабочем массиве псевдослучайную последовательность использовать в качестве индекса при обращении к дополнительному массиву(списку).

О некоторых ограничениях метода.
1. Поскольку рабочий(ие) массив(ы) располагаются в оперативной памяти компьютера, то размеры псевдослучайной последовательности ограничены. Особенно это касается 32-х разрядных ОС. Если в Вашем компьютере не меньше 1 Гб ОЗУ, то разумным ограничением будет порядка 100 млн.
2. Перемешивание может занять существенное время. На медленных системах, при озвученном выше числе это может вылиться в несколько секунд.
3. Сам по себе встроенный генератор случайных чисел компилятора имеет ограничения. В случае необходимости - пользуйтесь самописным.

(c)2011, Cepreu4.
Оригинальная статья была написана для GraBBerZ.CoM
При копировании ссылка на оригинал желательна.