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

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 6

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 7

Ruby, 32 bytes

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

Try it online!

Answer 8

Mathematica, 19 bytes

RandomChoice[#->#]&

Answer 9

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

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 13

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 14

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 15

05AB1E, 9 bytes

εD¸.×}˜.R

Try it online!

Answer 16

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 17

CJam, 5 bytes

lS/mR

Try it online! Note: seperate numbers by a space

Answer 18

Japt, 7 6 bytes

cÈÇX
ö

Try it

cÈÇX\nö     :Implicit input of array U
c           :Flat map by
 È          :Passing each X through the following function
  ÇX        :  Map the range [0,X) to X
    \n      :Reassign to U
      ö     :Random element

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

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 24

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

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 28

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

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.