PERL: БИБЛИОТЕКА ПРОГРАММИСТА


PERL: БИБЛИОТЕКА ПРОГРАММИСТА - стр. 142


§processes = (  1,   2,   3,   4,   5 ),

while (1)  {

Sprocess = grab_and_rotate(@>processes), print    Handling process $process\n", sleep 1,

> Смотри также---------------------------------------------------------------------------------------------

Описание функций unshift и push в perlfunc(l); рецепт 13.13.


144   Глава 4 • Массивы

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

Проблема

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

Решение

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

U fisher_yates_shuffle ( \@array )      генерация случайной перестановки # массива @аггау на месте sub fisher_yates_shuffle  < my $array = shift, my $i,

for ($i = @$array,   --$i,   )  { my $] = int rand ($i+1), next if $i == $], @$array[$i,$j] = @$array[$j,$i],

fisher_yates_shuffle(  \@array ),     ft Перестановка массива @array на месте

Или выберите случайную перестановку, воспользовавшись кодом из примера 4.4:

Spermutations = factorial^  scalar @array ),

@shuffle = @>array [  n2perm(  1+int(rand Spermutations),   $#array)  ],

Комментарий

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

sub naive_sriuffle {                                                  # Не делайте так1
for (my $i = 0,   $i < §_,   $i++) {

my $j = int rand @_,                                 # Выбрать случайный элемент

($_[$i],   $_[$j]) = ($_[$j],   $_[$i]),  # Поменять местами

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




- Начало -  - Назад -  - Вперед -