Échantillonner une séquence aléatoire non décroissante

20

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.

DJMcMayhem
la source
La sortie du nombre de séquences non décroissantes pour n, k pourrait être un défi intéressant en soi, si cela n'a pas déjà été fait ...
ETHproductions
1
@ETHproductions Pas vraiment, c'est juste un binôme (lié à cela )
Sp3000
@ Sp3000 Ah, OK. C'était un défi amusant pour moi de comprendre comment le calculer efficacement.
ETHproductions
Votre exigence selon laquelle chaque séquence a une probabilité égale d'être sortie n'est pas possible de satisfaire avec la plupart des PRNG de variétés de jardin qui peuvent avoir seulement des états de 32 ou 48 bits. Selon Wolfram, il y a 535 quintillions de 20 sous-séquences d'éléments de 1, ..., 100 (n'a pas vérifié combien d'entre elles ne diminuent pas). 2 ^ 64 n'est que de 18 quintillions.
Sinan Ünür

Réponses:

1

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.
Sherlock9
la source
13

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.

xnor
la source
C'est impressionnant. Pourriez-vous ajouter une explication de la méthode s'il vous plaît?
Yup, occupé maintenant, expliquera plus tard.
xnor
J'ai compté 90 octets ... (et vous pouvez aussi import*économiser 1 octet)
Rod
@Rod Merci, j'ai oublié ça.
xnor
7

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
Emigna
la source
7

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

xnor
la source
Est-ce que numpy aiderait ici?
@Lembik Bien pensé, mais il semble que vous deviez importer numpy.random, ce qui est trop long.
xnor
5

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--]
ETHproductions
la source
2

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.

TiKevin83
la source
1

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
aross
la source
D'abord JavaScript et maintenant PHP. Tous les meilleurs langages de programmation scientifique :) Merci.
@Lembik, vous êtes les bienvenus. Attention, il utilise un PRNG de base. Ne pas utiliser pour des trucs cryptographiques . :)
aross