Хотя ответ @ashawley уже принят, я не думаю, что он правильный. Я думаю, что на самом деле это ошибка, и она была введена коммитом erik-stripe на 1 сентября 2016 г. и ошибка действительно в строке

      val i = (x & 0x7fffffff).toInt % n

и это должно было быть

      val i = (x & 0x7fffffff).toInt % count

что еще не совсем правильно.

Я также ожидаю, что ваши 33% для последнего значения на самом деле 100%, и вы не учли тот факт, что вы выбрали 3 элемента, поэтому вся ваша статистика должна быть умножена на 3. Итак, для 3 -element selection последний элемент выбирается 100%, предыдущий - 66,6% и так далее, что даже хуже, чем вы ожидали.

Вот еще раз выдержка из кода:

else gen { (p, seed0) =>
  val buf = ArrayBuffer.empty[T]
  val it = l.iterator
  var seed = seed0
  var count = 0
  while (it.hasNext) {
    val t = it.next
    count += 1
    if (count <= n) {
      buf += t
    } else {
      val (x, s) = seed.long
      val i = (x & 0x7fffffff).toInt % n
      if (i < n) buf(i) = t
      seed = s
    }
  }
  r(Some(buf), seed)
}

Так что же этот код должен делать и что он делает на самом деле? Ветка if (count <= n) заполняет вывод buf первыми n элементами, после чего всегда работает ветвь else. Чтобы было понятнее, я изменил while перемещение if наружу на следующий код:

  for (i <- 0 until  n) {
    val t = it.next
    buf += t
  }
  while (it.hasNext) {
    val t = it.next
    val (x, s) = seed.long
    val i = (x & 0x7fffffff).toInt % n
    if (i < n) buf(i) = t
    seed = s
  }

Итак, теперь становится очевидным, что ветвь else должна одновременно решить, следует ли добавить текущий элемент в вывод buf И какой элемент там он должен заменить. Очевидно, что текущий код всегда выбирает каждый элемент, потому что if (i < n) всегда истинно, учитывая, что i вычисляется как something % n. И именно поэтому вы видите такой огромный перекос в последних элементах.

Очевидно, планировалось использовать модифицированную версию перемешивания Фишера-Йейтса. который выбирает только первые n элементов перетасовки, и чтобы сделать это правильно, вам нужно выбрать случайные числа в диапазоне [0, count) и, вероятно, поэтому код написан так, как он написан, т.е. сохраняет counter внутри while цикла.

Использование % count по-прежнему не совсем правильно, потому что такой простой способ не дает равномерного распределения, когда count не является степенью двойки. Чтобы быть более справедливым, что-то вроде

    val c0 = choose(0, count-1)
    val rt: R[Int] = c0.doApply(p, seed)        
    seed = rt.seed      
    val i = rt.retrieve.get // index to swap current element with. Should be fair random number in range [0, count-1], see Fisher–Yates shuffle
    if (i < n) buf(i) = t

или какой-либо другой способ создать i как справедливое равномерно распределенное случайное число в таком диапазоне.

Обновить (почему просто % count неправильно)

Вы можете посмотреть java.util.Random.nextInt(int) реализация или org.scalacheck.Choose.chLng для примера того, как это должно быть сделано. Это сложнее, чем просто % count, и на это есть веская причина. Чтобы проиллюстрировать это, рассмотрим следующий пример. Предположим, что ваш исходный генератор случайных чисел генерирует равномерно случайные 3-битные значения, то есть в диапазоне только [0, 7], и вы хотите получить случайное число в диапазоне [0, 2], и вы делаете это, просто выполнив

srcGenerator.nextInt() % 3

Теперь рассмотрим сопоставление значений в диапазоне [0, 7] с вашим диапазоном [0, 2]:

• 0, 3, 6 будет сопоставлено с 0 (т.е. сопоставляются 3 значения)
• 1, 4, 7 будет сопоставлено с 1 (т.е. сопоставляются 3 значения)
• 2, 5 будет сопоставлено с 2 (т.е. сопоставлены только 2 значения)

Итак, если вы сделаете только % 3, ваше распределение будет 0 - 3/8, 1 – 3/8, 2 – 2/8, что явно неравномерно. Вот почему те реализации, на которые я ссылался ранее, используют своего рода цикл и отбрасывают некоторые значения, сгенерированные генератором исходного кода. Требуется произвести однородную раздачу.

Не думаю, что это связано с семенами. Это имеет прямое отношение к эвристике Скалачека.

Есть тонкий баг. Подумайте, что он делает. Он заставляет себя выбирать значения в начале, а затем случайным образом перезаписывать их после этого:

while (it.hasNext) {
  val t = it.next
  count += 1
  if (count <= n) {
    buf += t
  } else {
    val (x, s) = seed.long
    val i = (x & 0x7fffffff).toInt % n
    if (i < n) buf(i) = t
    seed = s
  }
  ...

Он случайным образом присваивает эти элементы результату в else-блоке, поэтому отдает предпочтение хвостовым значениям.

Итак, pick случайным образом выбирает значения из набора. Однако он пожертвовал равнозначным выбором значений и отдает предпочтение концу списка, потому что код пытается лениво перебирать список.

Чтобы попытаться получить равномерное распределение выбранных элементов, вам нужно знать длину коллекции, но, как предполагает мой ответ, это невозможно без двойного использования итерации.

Возможно, если вы выберете reverse в своем списке или shuffle, вы получите лучшее распределение выборов с pick.

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

Обновлять

Но, как указывает Алексей Романов, это должно реализовать алгоритм отбора проб из резервуара, который позволяет избежать знания длины и может выполняться за время O(n). Просто дефект в коде. Исправление просто исправляет строку для генерации случайных чисел. Он должен получить случайное число от 1 до k-го (count) элемента, посещенного в списке.

val i = (x & 0x7fffffff).toInt % n

Должно быть:

val i = (x & 0x7fffffff).toInt % count

Я отправил PR в Scalacheck:

https://github.com/rickynils/scalacheck/pull/333