Sélection aléatoire dans un tableau

19

Ce défi est assez simple:
vous disposez d'un tableau d'entiers positifs (non compris 0) et devez sélectionner un élément aléatoire dans ce tableau.

Mais voici la torsion:
La probabilité de sélectionner un élément dépend de la valeur de l'entier, ce qui signifie que plus le nombre augmente, plus sa probabilité d'être sélectionné l'est aussi!

Exemple

On vous donne le tableau [4, 1, 5].

La probabilité de sélectionner 4 est égale à 4 divisée par la somme de tous les éléments du tableau , dans ce cas 4 / ( 4 + 1 + 5 ) = 4 / 10 =40%.
La probabilité de sélectionner 1 est 1 / 10ou 10%.

Contribution

Un tableau d'entiers positifs.

Production

Renvoyez l'entier sélectionné si vous utilisez une méthode, ou imprimez-le directement dans stdout.

Règles

  • C'est le donc le code le plus court en octets dans n'importe quelle langue gagne.
  • Les failles standard sont interdites.
Ian H.
la source

Réponses:

20

Gelée , 3 octets

x`X

Essayez-le en ligne!

Écoute, pas d'Unicode!

Explication:

x`X
 `  Make monad from dyad and use same left and right arguments
x   Repeat each element of the left argument (implicit) list its respective number of times in the right argument list
  X Random element
Erik le Outgolfer
la source
1
Pouvez-vous expliquer ce que fait votre code, s'il vous plaît? :)
Ian H.
1
@IanH. C'est vraiment un algorithme simple, répétez chaque élément lui-même fois puis choisissez au hasard.
Erik the Outgolfer du
16

R , 25 octets

function(s)sample(s,1,,s)

Essayez-le en ligne!

Explication:

function(s){
 sample(x = s, size = 1, replace = FALSE, prob = s)
}

Prend un échantillon sde taille 1sans remplacement, avec des poids s; ceux-ci sont redimensionnés pour être des probabilités.

Pour vérifier la distribution, utilisez ce lien .

Giuseppe
la source
tu m'as battu de 9 mois! : D
JayCe
@JayCe heh, mon seul avantage sur vous semble être "aller en premier" car vous êtes tout à fait le golfeur! :-)
Giuseppe
13

Pyth , 4 octets

OsmR

Essayez-le ici.

Sauvegardé d'un octet, grâce à @Jakube, avec une approche assez inhabituelle.

Pyth , 5 octets

Osm*]

Essayez-le ici!

Comment?

#1

OsmR - Programme complet.

   R - Carte de droite ...
  m - ... Utilisation de la carte. Cela crée essentiellement la liste [[4,4,4,4], [1], [5,5,5,5,5]].
       - ... Le mérite en revient à Jakube!
 s - Aplatir.
O - Élément aléatoire de ^. Afficher implicitement.

# 2

Osm *] - Programme complet.

  m - Carte sur l'entrée.
    ] - L'élément courant, d, enveloppé; [ré].
   * - Répétition d fois.
 s - Aplatir.
O - Élément aléatoire. Imprime implicitement le résultat.
M. Xcoder
la source
1
Je peux le faire en 4. Dois-je le gâcher, ou voulez-vous le trouver par vous-même?
Jakube
2
@Jakube Attendez un tout petit peu. Je veux voir si je peux le faire. Est-ce si évident?
M. Xcoder
1
@Jakube Ok, je vais cingler quand j'abandonne.
M. Xcoder
1
OsmLouOsmR
Jakube
1
@Jakube Ooh c'est très intelligent! Argument implicite d, puis cartographie dsur une plage ... génie!
Erik the Outgolfer du
8

CJam (9 octets)

q~_]ze~mR

Démo en ligne . Il s'agit d'un programme complet qui prend l'entrée au format tableau CJam sur stdin et imprime l'élément sélectionné sur stdout.

Dissection

q~   e# Read and parse input
_]z  e# Copy and transpose
e~   e# Run-length decode
mR   e# Select random element uniformly
Peter Taylor
la source
1
Un golf si puissant pour une tâche aussi simple.
Erik the Outgolfer le
7

Perl 6 , 20 octets

1 octet enregistré grâce à @Brad Gilbert b2gills.

{bag(@_ Zxx@_).pick}

Essayez-le en ligne!

Cela prend 1 argument de liste. Nous compressons 2 copies de cette liste en utilisant l' xxopérateur. Donc, avec @_ Zxx@_, nous obtenons une liste dans laquelle l'élément xest présenté xfois. Il est ensuite contraint Bag, qui est une collection qui stocke des objets ainsi que le nombre de fois qu'ils apparaissent dans la collection. Enfin, nous choisissons un élément aléatoire de cette collection avec pick, qui prend les comptes en compte et fait The Right Thing ™.

Ramillies
la source
Cela peut être raccourci à{bag(@_ Z=>@_).pick}
Brad Gilbert b2gills
@ BradGilbertb2gills, malheureusement cela ne fonctionne pas. Il fait un sac à partir des paires (il n'y aurait donc pas "1" une fois, "2" deux fois etc., mais "1 => 1" une fois, "2 => 2" également une fois etc. - pas ce que je veux) . C'est parce que les compositeurs ne sont pas des coerciteurs, comme expliqué dans ce calendrier de l'Avent .
Ramillies
@ BradGilbertb2gills, mais merci quand même, vous m'avez aidé à jouer au golf dans certains espaces ici et dans d'autres défis aussi!
Ramillies
Je voulais dire{bag(@_ Zxx@_).pick}
Brad Gilbert b2gills
Aah, je vois. Pourquoi cela ne m'est pas venu à l'esprit ...: -) Merci.
Ramillies du
6

Python 3.6 , 44 octets

lambda A:choices(A,A)[0]
from random import*

Oui pour les intégrés. L'autre Adans choices(A, A)est un weightsargument facultatif .

Essayez-le en ligne!

shooqie
la source
5

MATL , 8 6 octets

tY"1Zr

Essayez-le sur MATL Online!

Explication

t    % Implicit input. Duplicate
Y"   % Run-length decoding
1Zr  % Randomly take one value with uniform distribution. Implicitly display
Luis Mendo
la source
5

Mathematica, 19 octets

RandomChoice[#->#]&
J42161217
la source
4

Java (OpenJDK 8) , 88 87 86 83 octets

a->{int r=0,x=-1;for(int i:a)r-=i;for(r*=Math.random();r<1;)r+=a[++x];return a[x];}

Essayez-le en ligne!

Nevay
la source
Pourriez-vous ajouter une explication? J'essaie de comprendre pourquoi cela for(r*=Math.random();;)est nécessaire, ou si tout ce dont vous avez besoin est r*=Math.random().
Ayb4btu
@ Ayb4btu Sans la for(;;)boucle, cela nécessiterait une seconde instruction de retour (jamais atteinte) après le for(int i:a)...pour satisfaire le compilateur - ce qui serait 3 octets de plus.
Nevay
Ah, bien sûr, vous for(int i:a)êtes comme un foreachC #. J'ai eu le même problème, mais j'ai juste utilisé un forqui boucle continuellement. Votre nouvelle réponse m'intrigue, je pourrais essayer de chaparder certaines de vos idées.
Ayb4btu
3

J, 8 7 8 octets

Le 7 octet n'est pas valide; Je reviendrai sur une modification précédente lorsque je reviendrai sur mon ordinateur dans un jour ou deux.

Essayez-le en ligne!

?@+/{#~

:( la sélection d'éléments aléatoires dans un tableau est coûteuse.

8 octets

#~{~1?+/

9 octets

(1?+/){#~

Explication

?@+/{#~
?        Choose random number in range
  +/     Sum of the array
    {    Select that element from
     #~  The elements duplicated as many times as their value
cole
la source
?@+/est (?@+)/; Je crains que vous n'ayez à repousser cela jusqu'à 8 à nouveau…
FireFly
@FireFly J'aurais dû le tester davantage, bonne prise.
cole
3

JavaScript (ES6), 50 octets

a=>a.sort((a,b)=>b-a)[Math.random()**2*a.length|0]

Si tout va bien il est évident comment cela fonctionne, mais je l'expliquerai quand même ici. Il trie les entiers par ordre décroissant, puis en choisit un au hasard avec une distribution bêta (1 / 2,1) .

kamoroso94
la source
Je ne pense pas que cela aura la bonne distribution. Mes tests montrent qu'avec a=[4,1,5], vous obtiendrez environ 18% 1, 24% 4et 58% 5, ce qui suggère que vous obtiendrez cette distribution avec n'importe quelle entrée de longueur 3.
Giuseppe
Cela me semble correct. Entier supérieur, probabilité plus élevée.
kamoroso94
Oh je vois. J'ai mal lu la question. Excellente solution, +1!
Giuseppe
2

PowerShell , 27 octets

($args[0]|%{,$_*$_})|Random

Essayez-le en ligne!

Prend l'entrée $args[0]comme un tableau littéral. Boucle à travers chaque élément |%{...}et chaque itération construit un nouveau tableau ,$_d' $_éléments - par exemple, pour 4cela va créer un tableau @(4,4,4,4). Ces éléments du tableau sont ensuite canalisés dansGet-Random lesquels arrachera l'un des éléments avec une probabilité (pseudo) égale. Puisque, par exemple, @(4,1,5)cela nous donne @(4,4,4,4,1,5,5,5,5,5)cela satisfait aux exigences de probabilité.

AdmBorkBork
la source
2

C # (.NET Core) , 93 89 87 76 + 18 = 94 octets

a=>{int i=-1,r=new Random().Next(a.Sum());while(r>=0)r-=a[++i];return a[i];}

Essayez-le en ligne!

18 octets supplémentaires pour using System.Linq;

Remerciements

11 octets économisés grâce à Nevay, dont l'implémentation du nombre aléatoire était beaucoup plus concise (en plus d'être un intau lieu d'un double).

Dégolfé

a=>{
    int i=-1,
    r=new Random().Next(a.Sum());
    while(r>=0)
        r-=a[++i];
    return a[i];
}

Explication

Obtenez un nombre aléatoire r, entre 0 et la somme des éléments. Ensuite, à chaque itération, soustrayez l'élément courant r. Si rest inférieur à 0, renvoyez cet élément. L'idée est qu'il existe de plus grandes parties du nombre aléatoire pour les plus grands nombres dans le tableau.

Ayb4btu
la source
94 octets:a=>{int i=-1,r=new Random().Next(a.Sum());for(;r>=0;)r-=a[++i];return a[i];}
Nevay
2

Japt , 7 octets

ËÆD
c ö

Testez-le ici


Explication

Entrée implicite du tableau U.

Ë

Mappez sur le tableau en passant chaque élément à travers une fonction où Dest l'élément actuel.

ÆD

Générez un tableau de longueur Det remplissez-le avec D.

c

Aplatir.

ö

Obtenez un élément aléatoire.

Hirsute
la source
1

Perl, 31 octets

@a=map{($_)x$_}@ARGV;$a[rand@a]

Cela suppose que l'entrée est des arguments de ligne de commande. Notez qu'il peut manquer de mémoire si les nombres sont importants.


la source
1

Fusain , 12 octets

F⪪θ;FIι⊞υι‽υ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Étant donné que Charcoal essaie d'être trop intelligent, je dois utiliser une entrée délimitée par des points-virgules pour le tableau. Explication:

  θ             Input variable as string
 ⪪ ;            Split on semicolons
F               Loop i over each string
     Iι         Cast i to integer
    F           Repeat that many times
       ⊞υι      Push i to (originally empty) list
          ‽υ    Random selection from list
                Implicitly print
Neil
la source
1

Javascript (ES6), 61 54 octets

-7 octets grâce à @Justin Mariner

a=>a.find(m=>(n-=m)<0,n=Math.random()*eval(a.join`+`))

Exemple d'extrait de code

f=
a=>a.find(m=>(n-=m)<0,n=Math.random()*eval(a.join`+`))
console.log(f([4,1,5]))

Herman L
la source
Vous pouvez additionner en utilisant eval(a.join`+`)au lieu de reduce.
Justin Mariner
Si vous êtes d'accord avec ES7 +, vous pouvez utiliser: [].find(m=>(n-=m)<0,n=Math.random()*eval(a.join+ ))et appeler avecinput::[].find(...)
Downgoat
1

Haskell , 78 77 octets

import System.Random
f l=randomRIO(0,sum l-1)>>=pure.((l>>= \n->n<$[1..n])!!)

Essayez-le en ligne! Exemple d'utilisation: f [1,99]donne probablement99 .

Explication:

  • fprend une liste d'entiers let retourne l'entier sélectionné au hasard commeIO Int .
  • l>>= \n->n<$[1..n]construit une liste avec chaque élément nrépété plusieurs nfois.
  • randomRIO(0,sum l-1) renvoie un entier compris entre 0 et la longueur de la liste des éléments répétés, qui est exactement la somme de tous les éléments, moins un pour éviter une exception hors limite.

Bonus: version sans point de 85 octets

import System.Random
(>>=).randomRIO.(,)0.pred.sum<*>(pure.).(!!).(>>= \n->n<$[1..n])

Essayez-le en ligne!

Laikoni
la source
1

Java 8, 127 122 121 bytes

import java.util.*;a->{List l=new Stack();for(int i:a)for(int j=i;j-->0;Collections.shuffle(l))l.add(i);return l.get(0);}

-1 byte thanks to @Nevay.

Uses a similar approach as @ErikTheOutgolfer's Jelly answer, by adding n times the item n to the list, and then select one randomly from that list.

Explanation:

Try it here.

import java.util.*;        // Required import for List, Stack and Collections
a->{                       // Method with integer-array parameter and integer return-type
  List l=new Stack();      //  Create a List
  for(int i:a)             //  Loop (1) over the input array
    for(int j=i;j-->0;     //   Inner loop (2) from `i` down to 0
        Collections.shuffle(l))
                           //   and shuffle the List randomly after every iteration
      l.add(i);            //    Add `i` that many times to List `l`
                           //   End of inner loop (2) (implicit / single-line body)
                           //  End of loop (1) (implicit / single-line body)
  return l.get(0);         //  And then return the first item of the list
}                          // End of method
Kevin Cruijssen
la source
1
You can move the #shuffle call into the for loop to save 1 byte for(int j=i;j-->0;Collections.shuffle(l))l.add(i);.
Nevay
@Nevay Thanks! Shuffling the List after every iteration is pretty inefficient, but what do we care about efficiency, warnings and such when we can get rid of one additional pesky byte. ;p
Kevin Cruijssen
1

Dyalog APL, 8 bytes

/⍨⌷⍨1?+/

Try it online!

How?

  • /⍨, n copies of n for each n in the argument.
  • ⌷⍨, at the index of
  • 1?, a random value between 1 and
  • +/, the sum of the argument
Zacharý
la source
1

GNU APL 1.2, 26 23 bytes; 1.7 21 19 bytes

Approach inspired by Erik the Outgolfer's Jelly answer. Relies on ⎕IO being 0 instead of 1, which is the default for GNU APL (sort of +5 bytes for ⎕IO←0).

-3, -2 bytes thanks to @Zacharý

function form

∇f R
S[?⍴S←∊0 0⍉R∘.⍴R]∇

Anonymous lambda form

{S[?⍴S←∊0 0⍉⍵∘.⍴⍵]}

For the explanation, I will use to represent the argument passed to the function, but it is equivalent to R in the form.

⍵∘.⍴⍵ computes the outer product on the list using the reshape () operator. Effectively, this creates a table (like a multiplication table) but instead of multiplying, it repeats the element in the column a number of times equal to the element in the row. For the example given in the question, this is:

4 4 4 4    1 1 1 1    5 5 5 5   
4          1          5         
4 4 4 4 4  1 1 1 1 1  5 5 5 5 5

0 0⍉⍵∘.⍴⍵ transposes the matrix and returns just the main diagonal. This gives us just the parts where the row and column in ⍵∘.⍴⍵ were the same i.e. we repeated the number a number of times equal to its value. For the example, this is:

4 4 4 4  1  5 5 5 5 5

turns its argument into a list. Using the transpose () operator, we got a vector containing 3 vectors. Enlist () turns it into a single vector containing all the elements.

S←... assigns this new vector to vector S. ⍴S gives us the length of that list. ? is the random operator, so ?⍴S gives us a random number between 0 and the length of the list (exclusive) (this is why it relies on ⎕IO being 0; otherwise it's between 1 and the length, inclusive). S[...] returns the element at the given index.

Arc676
la source
You don't need Q, since you never use it. And IIRC you can remove the newline before the del (little triangle-thing marking the end of the function.)
Zacharý
Wow, I never new <IO> <IO>⍉ to get the main diagonal was even a thing!
Zacharý
@Zacharý Right, thanks. Frankly, I didn't even know about the transpose thing until I tried this task either. Found it here
Arc676
Oh, there does exist a much better free APL than GNU, it's called ngn APL. It's actually pretty cool! (ngn.github.io/apl/web, but it doesn't have tradfn)
Zacharý
@Zacharý I have that one too :) unfortunately the transpose function doesn't work (or I missed something). I will be testing it again now that I have a better understanding of how it works.
Arc676
1

MATLAB, 30 bytes

@(a)datasample(repelem(n,n),1)

This assumes MATLAB R2015a or newer and with the Statistics & Machine Learning toolbox installed.

See the explanation below for how repelem is used. The difference between this shorter one and the one below is that the S&ML toolbox includes the function datasample which can be used to take one or more elements from an array at random (with uniform probability) which allows an anonymous function to be used, stripping away the input/disp calls.

MATLAB, 49 bytes

n=input('');a=repelem(n,n);disp(a(randi(nnz(a))))

This code assumes that MATLAB R2015a or newer is used as that is when the repelem function was introduced. repelem is a function which takes two parameters, the first is an array of numbers to be replicated, and the second is an array of how many times the corresponding element should be replicated. Essentially the function performs run-length decoding by providing the number and the run-length.

By providing the same input to both inputs of repelem we end up with an array which consists of n times more of element n if that makes sense. If you provided [1 2 3] you would get [1 2 2 3 3 3]. If you provided [1 2 4 2] you would get [1 2 2 4 4 4 4 2 2]. By doing this it means that if we select an element with uniform probability (randi(m) gives a random integer from 1 to m with uniform probability), each element n has an n times higher probability of being selected. In the first example of [1 2 3], 1 would have a 1/6 chance, 2 would have a 2/6 chance and 3 would have a 3/6 chance.


As a side note, because repelem is not available yet for Octave, I can't give a TIO link. Additionally because Octave can't be used there is a big character penalty as input() and disp() need to be used as an anonymous function is not possible. If Octave supported repelem, the following could be used:

@(n)a(randi(nnz(a=repelem(n,n))))

That would have saved 16 bytes, but it was not to be.

Tom Carpenter
la source
Really appreciate the explanation, thanks!
Ian H.