Является ли Collections.shuffle () действительно случайным?Практические примеры, кажется, опровергают это утверждение

Question

У меня есть 1000 уникальных объектов в java.util.List, каждый из которых ссылается на изображение, каждое изображение в списке 1000 уникально, и теперь я хотел бы перетасовать их, чтобы я мог использовать первые 20 объектов и представить их на сайт-пользователя. Затем пользователь может нажать кнопку со словом «Перемешать», и я снова получаю 1000 изображений с нуля и снова вызываю shuffle(). Однако, похоже, что из 1000 объектов изображений я очень часто вижу одно и то же изображение снова и снова между 20-ю выборками изображений.

Кажется, что-то не так, лучше совет, советы?

Мой код очень прост:

List<String> imagePaths = get1000Images();
Collections.shuffle(imagePaths);

int i = 0;
for (String path: imagePaths) {
  ... do something with the path ...
  i++;
  if (i >= 20) break;
}

Я знаю, что Collections.shuffle() хорошо распределен: см. например http://blog.ryanrampersad.com/2012/03/03/more-on-shuffling-an-array-correctly/

Однако мне просто кажется, что вероятность увидеть одно и то же изображение снова и снова на наборе из 20 изображений из 1000 должна быть намного меньше ...

Входы высоко оценены.

Answer 1

Его человеческая природа - видеть узоры, которых там нет.Многие люди видят закономерности на планетах и ​​звездах, определяющие их жизнь.

В первых 1000 цифрах числа Пи шесть последовательных строк.Означает ли это, что цифры ПИ не случайны?нет.Шаблон больше не повторяется, чем вы ожидаете.

Сказав это, Random не является полностью случайным и будет повторяться после 2 ^ 48 вызовов.(он использует 48-битное начальное число). Это означает, что с его помощью невозможно произвести все возможные long или double.Если вы хотите больше случайности, вы можете вместо этого использовать SecureRandom с shuffle.

Похоже, что вы хотите, что-то вроде этого

List<String> imagePaths = new ArrayList<>();

// called repeatedly
if (imagePaths.size() <= 500) {
    imagePaths = get1000Images();
    Collections.shuffle(imagePaths);
}

for (String path: imagePaths.subList(0, 20)) {
  ... do something with the path ...
}

imagePaths = imagePaths.subList(20, imagePaths.size());

Это гарантирует, что вы не видите то же изображениеза последние 500 звонков.

Answer 2

Если вы показываете 20 изображений из 1000, вероятность увидеть любого из этих 20 , повторенных на следующей итерации, составляет приблизительно 0,34, поэтому вы не должны удивляться, увидев повторение изображений.

Шансы увидеть конкретное изображение по-прежнему один на тысячу, но если вы ищете двадцать изображений, шансы намного выше.

Мы можем вычислить вероятность того, что ни одно из предыдущих 20изображения повторяются как:

 980   979         961
———— × ——— × ... × ——— ≈ 0.66
1000   999         981

И поэтому вероятность увидеть повторение составляет один минус это, или приблизительно 0,34.

И вероятность увидеть изображение, повторенное в любом из следующих двухитерации:

1 - (0.66 × 0.66) ≈ 0.56

Другими словами, более вероятно, что вы увидите повторное изображение в течение двух следующих циклов.(И это не включает изображения, повторенные из второго цикла в третьем, что только увеличит его вероятность.)

Для чего стоит, вот некоторый Java-код для выполнения вышеуказанного вычисления:

float result = 1.0f;
int totalImages = 1000;
int displayedImages = 20;

for (int i = 0; i < displayedImages; i++) {
  result = result * (totalImages - displayedImages - i) / (totalImages - i);
}

System.out.println(result);

Answer 3

Ваша интуиция верна для определенного изображения [вы вряд ли увидите конкретное изображение снова и снова], но не для общего изображения [вы, вероятно, увидите какое-то изображение повторяется].Это одно из таких мест с вероятностью того, что наша автоматическая интуиция неправильна ...

Это напоминает мне парадокс дня рождения , который противоречит интуиции и говоритдля группы из 23 человек вероятность того, что у 2 из них будет один и тот же день рождения, равна 0,5, что намного больше, чем ожидает интуиция!

Answer 4

Я четыре раза перемешал 52 карты и отмечал каждый раз, когда каждая итерация повторяла одну и ту же карту в одном и том же слоте, что давало мне примерно 14 из 208 карт, что было примерно на 93,3% случайным.

Answer 5

После вашего вопроса я написал следующую программу. Я создал список последовательных целых чисел и перемешал его 10, 100, 1000 и 10000 раз. После каждой серии перемешиваний я проверял значение элемента в 5-й позиции массива и создавал массив счетчиков: сколько раз каждое число появляется в 5-й позиции.

Вот программа:

public class MyTest {
    public static void main(String[] args) {
        int n = 10;
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0;  i < n;  i++) {
            list.add(i);
        }

        int[] counters = new int[n];

        for(int shuffles : new int[] {10, 100, 1000, 10000}) {
            Arrays.fill(counters, 0);
            for (int i = 0;  i < shuffles; i++) {
                Collections.shuffle(list);
                // check 5-th element
                int fifth = list.get(5);
                counters[fifth] = counters[fifth] + 1;
            }
            System.out.println(shuffles + ": " + Arrays.toString(counters));
        }
    }
}

А вот и результаты:

10: [0, 1, 1, 1, 2, 0, 0, 3, 2, 0] 100: [11, 9, 9, 7, 10, 12, 13, 13, 8, 8] 1000: [100, 101, 107, 101, 95, 96, 109, 83, 93, 115] 10000: [1015, 942, 990, 1003, 1015, 1037, 977, 1060, 950, 1011]

Как видите, "случайность" зависит от количества перемешиваний. Если вы перемешиваете массив 10 раз, минимальный счетчик равен 0, а максимальный - 3. Разница между этими значениями для 100 перемешиваний (в процентах) значительно меньше. Цифры почти одинаковы для 10000 тасовок.

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

Пожалуйста, смотрите пост @amit, в котором описывается значение shuffle.

Итак, решение для вас - перетасовать ваш массив 10 раз.

РЕДАКТИРОВАТЬ: @ Дейв Уэбб дал идеальное объяснение случая.

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

Set<Image> show = new HashSet<Image>();
Random r = new Random(System.currentTimeMillis());
for (int i = 0;  show.size() < 20;  i++) {
    show.add(list.get(r.nextInt()));
}

Answer 6

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