Randomly select from an array

Question

This challenge is rather simple:
You are given an array of positive (not including 0) integers, and have to select a random element from this array.

But here's the twist:
The probability of selecting an element is dependent on the value of the integer, meaning as the integer grows larger, the probability of it to get selected does too!

Example

You are given the array [4, 1, 5].

The probability of selecting 4 is equal to 4 divided by the sum of all elements in the array, in this case 4 / ( 4 + 1 + 5 ) = 4 / 10 =40%.
The probability of selecting 1 is 1 / 10 or 10%.

Input

An array of positive integers.

Output

Return the selected integer if using a method, or directly print it to stdout.

Rules

• This is code-golf so shortest code in bytes in any language wins.
• Standard loopholes are forbidden.

Answer 1

Jelly, 3 bytes

x`X

Try it online!

Look 'ma, no Unicode!

Explanation:

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

Answer 2

R, 25 bytes

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

Try it online!

Explanation:

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

Takes a sample from s of size 1 without replacement, with weights s; these are rescaled to be probabilities.

To verify the distribution, use this link.

Answer 3

Pyth, 4 bytes

OsmR

Try it here.

Saved one byte, thanks to @Jakube, with a rather unusual approach.

Pyth, 5 bytes

Osm*]

Try it here!

How?

#1

OsmR   - Full program.

   R   - Right Map...
  m    - ... Using Map. This essentially creates the list [[4,4,4,4], [1], [5,5,5,5,5]]. 
       - ... Credit goes to Jakube for this!
 s     - Flatten.
O      - Random element of ^. Display implicitly.

#2

Osm*]   - Full program.

  m     - Map over the input.
    ]   - The current element, d, wrapped; [d].
   *    - Repeated d times.
 s      - Flatten.
O       - Random Element. Implicitly print the result.

Answer 4

CJam (9 bytes)

q~_]ze~mR

Online demo. This is a full program which takes input in CJam array format on stdin and prints the selected element to stdout.

Dissection

q~   e# Read and parse input
_]z  e# Copy and transpose
e~   e# Run-length decode
mR   e# Select random element uniformly

Answer 5

Perl 6, 20 bytes

Saved 1 byte thanks to @Brad Gilbert b2gills.

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

Try it online!

This takes 1 list argument. We zip 2 copies of this list using the xx operator. So with @_ Zxx@_, we get a list in which element x is presented x times. It is then coerced to Bag, which is a collection that stores objects along with how many times they appear in the collection. Finally, we pick a random element from this collection with pick, which takes the counts into the account and does The Right Thing™.

Answer 6

Python 3.6, 44 bytes

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

Yay for built-ins. The other A in choices(A, A) is an optional weights argument.

Try it online!

Answer 7

MATL, 8 6 bytes

tY"1Zr

Try it at MATL Online!

Explanation

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

Answer 8

Mathematica, 19 bytes

RandomChoice[#->#]&

Answer 9

Ruby, 32 bytes

->a{a.flat_map{|x|[x]*x}.sample}

Try it online!

Answer 10

Python 3, 62 bytes

lambda k:choice(sum([x*[x]for x in k],[]))
from random import*

Try it online!

Answer 11

Java (OpenJDK 8), 88 87 86 83 bytes

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

Try it online!

Answer 12

J, _{8 7} 8 bytes

The 7 byter is invalid; I'll revert this to a previous edit when I get back to my computer in a day or two.

Try it online!

?@+/{#~

:( selecting random elements from an array is costly.

8 bytes

#~{~1?+/

9 bytes

(1?+/){#~

Explanation

?@+/{#~
?        Choose random number in range
  +/     Sum of the array
    {    Select that element from
     #~  The elements duplicated as many times as their value

Answer 13

JavaScript (ES6), 50 bytes

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

Hopefully it's apparent how this works, but I'll explain it here anyway. It sorts the integers in descending order, then chooses one at random with a beta distrubution (1/2,1).

Answer 14

05AB1E, 9 bytes

εD¸.×}˜.R

Try it online!

Answer 15

PowerShell, 27 bytes

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

Try it online!

Takes input $args[0] as a literal array. Loops through each element |%{...} and each iteration constructs a new array ,$_ of $_ elements -- e.g., for 4 this will create an array @(4,4,4,4). Those array elements are then piped into Get-Random which will pluck out one of the elements with (pseudo) equal probability. Since, e.g., for @(4,1,5) this gives us @(4,4,4,4,1,5,5,5,5,5) this satisfies the probability requirements.

Answer 16

Japt, 7 bytes

ËÆD
c ö

Test it here

---

Explanation

Implicit input of array U.

Ë

Map over the array passing each element through a function where D is the current element.

ÆD

Generate an array of length D and fill it with D.

c

Flatten.

ö

Get a random element.

Answer 17

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

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

Try it online!

An extra 18 bytes for using System.Linq;

Acknowledgements

11 bytes saved thanks to Nevay, whose random number implementation was a lot more concise (as well as being an int instead of a double).

Degolfed

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

Explanation

Get a random number, r, between 0 and sum of elements. Then at each iteration subtract the current element from r. If r is less than 0, then return this element. The idea is that there are bigger portions of the random number for the larger numbers in the array.

Answer 18

CJam, 5 bytes

lS/mR

Try it online! Note: seperate numbers by a space

Answer 19

Perl, 31 bytes

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

This assumes the input to be command line arguments. Note that it may run out of memory if the numbers are large.

Answer 20

Perl 5, 31 + 1 (-a) = 32 bytes

@p=map{($_)x$_}@F;say$p[rand@p]

Try it online!

Answer 21

GolfScript, 17 bytes

~{.({.}*}%.,rand=

Try it online!

Answer 22

Charcoal, 12 bytes

Ｆ⪪θ;ＦＩι⊞υι‽υ

Try it online! Link is to verbose version of code. Since Charcoal tries to be too clever, I'm having to use semicolon-delimited input for the array. Explanation:

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

Answer 23

Javascript (ES6), 61 54 bytes

-7 bytes thanks to @Justin Mariner

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

Example code snippet

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

Answer 24

Haskell, 87 bytes

import System.Random
f l|m<-[x<$[1..x]|x<-l]>>=id=randomRIO(0,length m-1)>>=print.(m!!)

Try it online!

Answer 25

Haskell, 78 77 bytes

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

Try it online! Usage example: f [1,99] probably yields 99.

Explanation:

• f takes a list of integers l and returns the randomly selected integer as IO Int.
• l>>= \n->n<$[1..n] constructs a list with each element n repeated n times.
• randomRIO(0,sum l-1) yields an integer in the range from 0 to the length of the list of repeated elements, which is exactly the sum of all elements, minus one to avoid a out of bound exception.

---

Bonus: 85 byte point-free version

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

Try it online!

Answer 26

Bash, 51 bytes

for n in $@;{ printf $n\\n%.s `seq $n`;}|shuf|sed q

Takes space-separated or newline-separated input in one argument or multiple arguments.

Try it online!

Validate the random frequencies with a more complicated test case.

Answer 27

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

Answer 28

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.

Answer 29

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

Answer 30

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.

Answer 31

Perl 6, 21 bytes

{flat($_ Zxx$_).pick}

Try it online!

$_ Zxx $_ zips the input list with itself using the xx replication operator, turning (for example) (1, 2, 3) into ((1), (2, 2), (3, 3, 3)). flat flattens that into a list of integers, and finally pick picks one at random.

Answer 32

JavaScript ES6, 40 bytes.

(a)=>a[parseInt(Math.random()*a.length)]

Example

((a)=>a[parseInt(Math.random()*a.length)])([4,1,5])

Answer 33

Clojure, 64 bytes

(defn a[i](rand-nth(reduce #(concat %(take %2(repeat %2)))[]i)))

Appends each item item number of times to a new list, then takes a random element.

Finally a clojure answer that's not incredibly much longer than other answers :D

Answer 34

05AB1E, 21 bytes

O/ždT6m/svy-D0‹s})1kè

Try it online!

---

Here's a weird implementation for you, uses microseconds on the system's CPU for the randomized seed.

O/                     # [.4,.1,.5] | Push prob distribution.
  ždT6m/               # ?????????? | 0 < x < 100000 divided by 100000.
        s              # [.4,.1,.5] | Swap...
         v             # For each prob in distribution...
          y-           # Remove from random number b/w 0 and 1.
            D0‹        # Dupe each, find if this number made the random number less than 0.
               s})     # Continue loop, swapping current random diff to the front of the stack.
                  1kè  # First instance of the random number going negative is our random return.

Answer 35

Clojure, 46 bytes

(fn[s](rand-nth(flatten(map #(repeat % %)s))))

Try it online!

The usual Clojure pain: simple idea, long-ass (for golfing) function names.

Answer 36

TI-BASIC, 20 bytes

Ans→L₁
SortD(L₁
L₁(1+int(rand²dim(L₁

Input and output are stored in Ans. If you see a box, L₁ is L₁. Same algorithm as my JavaScript answer.