Образец случайной неубывающей последовательности

20

Входные данные: два целых числа n и k, заданные в любой форме, удобной для вашего кода

Выходные данные Случайная неубывающая последовательность из k целых чисел, каждое из которых находится в диапазоне от 1 до n. Выборка должна выбираться равномерно из всех неубывающих последовательностей из k целых чисел с целыми числами в диапазоне от 1 до n.

Вывод может быть в любом удобном для вас формате.

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

Можно предположить, что целые числа n, k> 0.

пример

Скажите n, k = 2. Неубывающие последовательности

1,1
1,2
2,2

Каждая последовательность должна иметь вероятность 1/3 вывода.

ограничение

Ваш код должен выполняться не более, чем за несколько секунд для k = 20 и n = 100.

Что не работает

Если вы просто случайным образом выберете каждое целое число из диапазона от 1 до n, а затем отсортируете список, вы не получите равномерного распределения.

DJMcMayhem
источник
Вывод числа неубывающих последовательностей для n, k может сам по себе создать интересную задачу, если это еще не сделано ...
ETHproductions
1
@ETHproductions Не совсем, это просто бином (связанный с этим )
Sp3000
@ Sp3000 Ах, хорошо. Для меня было забавной задачей выяснить, как рассчитать это эффективно.
ETHproductions
Ваше требование, чтобы каждая последовательность имела равную вероятность вывода, невозможно удовлетворить большинством PRNG садового сорта, которые могут иметь только 32- или 48-битные состояния. Согласно Вольфраму, есть 535 квинтиллионов 20 подпоследовательностей элементов 1, ..., 100 (не проверял, сколько из них не уменьшается). 2 ^ 64 - это всего 18 квинтиллионов.
Синан Юнюр

Ответы:

1

На самом деле , 14 12 байт

Этот ответ основан на 05AB1E ответ Emigna в и ответов на этот вопрос Math.SE . Предложения по игре в гольф приветствуются! Попробуйте онлайн!

;;ra+DR╚HS♀-

Ungolfing

      Implicit input n, then k.
;;    Duplicate k twice.
r     Push range [0...k] for later.
a     Invert the stack. Stack: n, k, k, [0...k]
+DR   Push the range [1..n+k-1].
╚     Shuffle the range. Stack: shuffled_range, k, [0...k]
H     Push the first k elements of shuffled_range. Call this increasing.
S     Sort increasing so the elements are actually increasing.
♀-    Subtract each element of [0...k] from each element of increasing.
      This gives us our non-decreasing sequence.
      Implicit return.
Sherlock9
источник
13

Python, 89 байт

from random import*
lambda n,k:[x-i for i,x in enumerate(sorted(sample(range(1,n+k),k)))]

Генерация возрастающей последовательности, а не неубывающей, была бы простой: это просто случайное подмножество kчисел между 1и n, отсортированными.

Но мы можем преобразовать возрастающую последовательность в неубывающую, уменьшив каждый разрыв между последовательными числами на 1. Таким образом, разрыв 1 становится разрывом 0, делая равные числа. Для этого уменьшите iнаибольшее значение наi

r[0], r[1], ..., r[n-1]  =>  r[0]-0, r[1]-1, ..., r[n-1]-(n-1)

Чтобы результат был от 1до n, входные данные должны быть от 1до n+k-1. Это дает биекцию между неубывающими последовательностями чисел между 1и n, к увеличивающимся последовательностям между 1и n+k-1. Та же биекция используется в аргументе звезд и столбцов для подсчета таких последовательностей.

В коде используется функция python random.sample, которая берет kобразцы без замены из списка ввода. Сортировка дает возрастающую последовательность.

XNOR
источник
Это впечатляет. Не могли бы вы добавить объяснение метода, пожалуйста?
Да, занят сейчас, объясню позже.
xnor
Я насчитал 90 байт ... (и вы также import*можете сэкономить 1 байт)
Род
@ Род Спасибо, я забыл об этом.
xnor
7

Python, 87 байт

from random import*
f=lambda n,k:k>random()*(n+k-1)and f(n,k-1)+[n]or k*[7]and f(n-1,k)

Вероятность включения максимально возможного значения nравна k/(n+k-1). Чтобы включить его, поместите его в конец списка и уменьшите оставшиеся необходимые числа k. Чтобы исключить это, уменьшите верхнюю границу n. Затем повторяйте до тех пор, пока значения больше не понадобятся ( k==0).

В Python, randomпохоже, нет встроенной переменной Бернулли: 1 с некоторой вероятностью и 0 в противном случае. Таким образом, это проверяет, randomпадает ли ниже случайное значение между 0 и 1, сгенерированное как k/(n+k-1). Python 2 будет отношение , как поплавок деление, таким образом , мы вместо того, чтобы умножить на знаменатель: k>random()*(n+k-1).

XNOR
источник
Поможет ли тут?
@Lembik Хорошая мысль, но похоже, что вам придется импортировать numpy.random, что слишком долго.
xnor
5

JavaScript (Firefox 30+), 74 байта

(n,k,i=0,j=k)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)i-j+k--]

объяснение

Отличный ответ xnor на Python содержит очень хорошее резюме того, как / почему работает техника, используемая здесь. Первым шагом является создание диапазона [1, 2, ..., n + k - 1] :

(n,k,i=0)=>[for(_ of Array(q=k+n-1))++i]

Далее нам нужно взять k случайных предметов из этого диапазона. Чтобы сделать это, нам нужно выбрать каждый элемент с вероятностью s / q , где s - количество элементов, которые все еще необходимы, а q - количество элементов, оставшихся в диапазоне. Поскольку мы используем понимание массива, это довольно просто:

(n,k,i=0)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)k--&&i]

Это дает нам равномерно распределенную возрастающую последовательность чисел. Это можно исправить, вычтя количество найденных ранее элементов j :

(n,k,i=0,j=0)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)k--&&i-j++]

Наконец, сохраняя k в j , мы можем включить k--в выражение и сохранить несколько байтов:

(n,k,i=0,j=k)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)i-j+k--]
ETHproductions
источник
2

TI-BASIC, 54 байта

Prompt N,K
K→dim(L1
While K
If rand<K/(N+K-1
Then
N→L1(K
K-1→K
Else
N-1→N
End
End
Disp L1

Следуйте логике xnor с небольшим предостережением. Мы можем теоретически побрить байт, выполнив что-то вроде этого:

K>rand(N+K-1

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

Это должно работать прилично быстро на 84+ за ограничение, но я проверю, когда смогу.

TiKevin83
источник
1

PHP, 77 75 73 байта

foreach(array_rand(range(2,$argv[1]+$k=$argv[2]),$k)as$v)echo$v+1-$i++,_;

Запустите так:

php -r 'foreach(array_rand(range(2,$argv[1]+$k=$argv[2]),$k)as$v)echo$v+1-$i++,_;' -- 10 5 2>/dev/null;echo
> 1_4_6_9_9_

объяснение

foreach(                    # Iterate over...
  array_rand(               #   a (sorted) random number of items from...
    range(                  #     an array with items...
      2,                    #       from 2
      $argv[1]+$k=$argv[2]  #       to n + k (set arg 2 to $k)
    ),
    $k                      #     Take k number of items (their keys)
  )
  as $v
)
  echo $v +1 - $i++,"_";    # Print the value subtracted by the index.
                            # Need to add 1, because keys are 0-indexed.

Tweaks

  • Сохраненные 2 байта путем удаления end()вызова и набора $argv[2]для $kвместо того, чтобы сокращенный доступа к аргументам
  • Сэкономили 2 байта, удалив индекс из foreach, поскольку это просто инкрементное число. Просто увеличивайте $iкаждую итерацию вместо
aross
источник
Сначала JavaScript, а теперь PHP. Все лучшие научные языки программирования :) Спасибо.
@Lembik, пожалуйста. Имейте в виду, он использует базовый PRNG. Не используйте для криптографических вещей . :)
aross