Почему я получаю неправильное случайное распределение с помощью Perl's List :: Util :: shuffle? - PullRequest
Новая
       14

Почему я получаю неправильное случайное распределение с помощью Perl's List :: Util :: shuffle?

0 голосов
/ 07 марта 2019

У меня есть коллекция из нескольких сотен виниловых пластинок, организованная в алфавитном порядке строкой идентификатора каталогаЯ написал скрипт, который случайным образом выбирает для меня 20 записей из моей коллекции путем выборки из перемешанного массива идентификаторов каталога.Тем не менее, я обнаружил, что часто распределение записей, которые он выбирает для меня, не является хорошим.Очень часто он выбирает 2 записи с последовательными идентификаторами каталога и / или несколько записей, сгруппированных близко друг к другу.При выборе 20 записей из 800 это случается очень редко.

Я сохраняю список идентификаторов каталогов в массиве @selection, и для случайной выборки из 20 элементов из этого массива я назначаю первый20 элементов из перемешанного массива: 

@selection = (shuffle @selection)[0 .. 19];

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

@selection = shuffle @selection; sleep 1;
@selection = reverse @selection; sleep 1;
@selection = (shuffle @selection)[0 .. 19];

1 Ответ

5 голосов
/ 07 марта 2019

Есть C (800, 20) = 3,73 × 10 39 способов выбора 20 наименований из 800.

Существует C (781, 20) = 2,29 × 10 39 способов выбора 20 названий из 800, где нет двух соседних. [1]

Таким образом, существует вероятность (2,29 × 10 39 ) / (3,73 × 10 39 ) = 61,4% вероятности выбора набора, не содержащего соседних заголовков.

Таким образом, есть шанс 1 - 61,4% = 38,6% выбрать набор, содержащий смежные заголовки.

Теперь, когда мы знаем, чего ожидать, давайте проверим shuffle.

Тест: 

#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw( shuffle );

my $num_tests = 100_000;
my $N = 800;
my @titles = 0..($N-1);
my $has_adjacent_titles = 0;
for (1..$num_tests) {
   my @shuffled_selection = ( shuffle(@titles) )[0..19];
   my @ordered = sort { $a <=> $b } @shuffled_selection;
   ++$has_adjacent_titles if grep { $ordered[$_-1]+1 == $ordered[$_] } 1..$#ordered;
}

printf "%.1f%%\n", $has_adjacent_titles / $num_tests * 100;

Вывод: 

>a.pl
38.6%

>a.pl
38.8%

>a.pl
38.5%

Похоже, shuffle работает довольно хорошо.

  1. См. Комбинаторное ограничение на выбор соседних объектов ,
...