Entrée: deux entiers n et k donnés sous n'importe quelle forme qui convient à votre code

Sortie Une séquence aléatoire non décroissante de k entiers, chacun compris entre 1 et n. L'échantillon doit être choisi uniformément parmi toutes les séquences non décroissantes de k entiers avec des entiers compris entre 1 et n.

La sortie peut être dans n'importe quel format raisonnable qui vous convient.

Vous pouvez utiliser n'importe quel générateur pseudo-aléatoire fourni par votre bibliothèque / langue préférée.

On peut supposer que les entiers n, k> 0.

Exemple

Disons n, k = 2. Les séquences non décroissantes sont

1,1
1,2
2,2

Chaque séquence doit avoir une probabilité de 1/3 d'être sortie.

Restriction

Votre code ne devrait pas s'exécuter en quelques secondes pour k = 20 et n = 100.

Ce qui ne marche pas

Si vous échantillonnez simplement chaque entier au hasard dans la plage de 1 à n, puis triez la liste, vous n'obtiendrez pas une distribution uniforme.

Réellement , 14 12 octets

Cette réponse est basée sur la réponse de 05AB1E de Emigna et les réponses sur cette question Math.SE . Suggestions de golf bienvenues! Essayez-le en ligne!

;;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 octets

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

Générer une séquence croissante plutôt qu'une séquence non décroissante serait simple: il s'agit simplement d'un sous-ensemble aléatoire de knombres entre 1etn , triés.

Mais, nous pouvons convertir une séquence croissante en une séquence non décroissante en réduisant chaque écart entre les nombres consécutifs de 1. Ainsi, un écart de 1 devient un écart de 0, ce qui rend des nombres égaux. Pour ce faire, diminuez la i'e valeur la plus élevée dei

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

Pour que le résultat soit de 1à n, l'entrée doit être de 1à n+k-1. Cela donne une bijection entre des séquences de nombres non décroissants entre 1et n, à des séquences croissantes entre 1et n+k-1. La même bijection est utilisée dans l' argument étoiles et barres pour compter ces séquences.

Le code utilise la fonction python random.sample, qui prend des kéchantillons sans remplacement dans la liste d'entrée. Le trier donne la séquence croissante.

05AB1E , 13 octets

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

Essayez-le en ligne!

Explication

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

Python, 87 octets

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)

La probabilité que la valeur maximale possible nsoit incluse est égale à k/(n+k-1). Pour l'inclure, placez-le à la fin de la liste et décrémentez les nombres nécessaires restants k. Pour l'exclure, décrémentez la limite supérieure n. Ensuite, répétez jusqu'à ce que plus aucune valeur ne soit nécessaire ( k==0).

Python randomne semble pas avoir de fonction intégrée pour une variable de Bernoulli: 1 avec une certaine probabilité, et 0 sinon. Ainsi, cela vérifie si une valeur aléatoire entre 0 et 1 générée par randomtombe en dessous k/(n+k-1). Python 2 serait le rapport que la division du flotteur, de sorte que nous à la place multiplier par le dénominateur: k>random()*(n+k-1).

JavaScript (Firefox 30+), 74 octets

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

Explication

L'excellente réponse de Python de xnor contient un très bon résumé de la façon / pourquoi la technique utilisée ici fonctionne. La première étape consiste à créer la plage [1, 2, ..., n + k - 1] :

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

Ensuite, nous devons prendre k éléments aléatoires de cette plage. Pour ce faire, nous devons sélectionner chaque élément avec la probabilité s / q , où s est le nombre d'éléments encore nécessaires et q est le nombre d'éléments restant dans la plage. Puisque nous utilisons une compréhension de tableau, c'est assez simple:

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

Cela nous donne une séquence croissante de nombres uniformément répartis . Cela peut être corrigé en soustrayant le nombre d'éléments j que nous avons précédemment trouvé:

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

Enfin, en stockant k dans j , nous pouvons incorporer k--dans l'expression et économiser quelques octets:

(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 octets

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

Suivez la logique de xnor, avec une petite mise en garde. Nous pourrions théoriquement raser un octet en faisant quelque chose comme ceci:

K>rand(N+K-1

Mais rand (est réservé pour créer une liste de nombres aléatoires, nous ne pourrions donc pas faire la multiplication implicite souhaitée pour enregistrer un octet.

Cela devrait fonctionner assez rapidement sur un 84+ selon la restriction, mais je vérifierai si je le peux.

PHP, 77 75 73 octets

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

Courez comme ceci:

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_

Explication

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

• Enregistré 2 octets en supprimant l' end()appel et défini $argv[2]à la $kplace pour raccourcir l'accès aux arguments
• Enregistré 2 octets en supprimant l'index de foreach, car il s'agit simplement d'un nombre incrémentiel. Incrémentez simplement $ichaque itération à la place