Входные данные: два целых числа 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, а затем отсортируете список, вы не получите равномерного распределения.

На самом деле , 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.

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образцы без замены из списка ввода. Сортировка дает возрастающую последовательность.

05AB1E , 13 байтов

+<L.r¹£{¹L<-Ä

Попробуйте онлайн!

объяснение

+<L            # range [1 ... n+k-1]
   .r          # scramble order
     ¹£        # take k numbers
       {       # sort
        ¹L<-   # subtract from their 0-based index
            Ä  # absolute value

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).

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--]

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+ за ограничение, но я проверю, когда смогу.

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каждую итерацию вместо