Perl. Библиотека программиста

Случайная перестановка элементов массива

Проблема

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

Решение

Каждый элемент массива меняется местом с другим, случайно выбранным элементом:

# fisher_yates_shuffle ( \@array ) : генерация случайной перестановки
# массива @аrrау на месте
sub fisher_yates_shuffle {
  my $array = shift;
  my $i;
  for ($i = @$array; --$i; ) {
     my $j = int rand ($i+1);
     next if $i == $j;
     @$array[$i,$j] = @$array[$j, $i];
  }
}
fisher_yates_shuffle( \@array );     # Перестановка массива @array на месте

Или выберите случайную перестановку:

$permutations = factorial ( scalar @array );
@shuffle = @array [ n2perm( 1 + int(rand $permutations), $#array) ];

Комментарий

Случайные перестановки на удивление коварны. Написать плохую программу перестановки очень просто:

sub naive_shuffle {                       # He делайте так!
  for (my $i = 0; $i < @_; $i++) {
     my $i = int rand @_;                 # Выбрать случайный элемент
    ($_[$i], $_[$j]) = ($_[$j], $_[$i]);  # Поменять местами
  }
}

Такой алгоритм является смещенным — один перестановки имеют большую вероятность, чем другие. Это нетрудно доказать: предположим, мы получили список из 3 элементов. Мы генерируем 3 случайных числа, каждое из которых может принимать 3 возможных значения — итого 27 возможных комбинаций. Однако для списка из трех элементов существует всего 6 перестановок. Поскольку 27 не делится на 6, некоторые перестановки появляются с большей вероятностью, чем другие.

В приведенном выше алгоритме Фишера—Йетса это смещение устраняется за чет изменения интервала выбираемых случайных чисел.

См. также

Описание функции rand