19
\$\begingroup\$

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 so shortest code in bytes in any language wins.
  • Standard loopholes are forbidden.
\$\endgroup\$

36 Answers 36

20
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Can you explain what your code does, please? :) \$\endgroup\$ – Ian H. Sep 14 '17 at 17:39
  • 1
    \$\begingroup\$ @IanH. It's really a simple algorithm repeat each element itself times then choose randomly. \$\endgroup\$ – Erik the Outgolfer Sep 14 '17 at 17:43
16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ you beat me to it by 9 months! :D \$\endgroup\$ – JayCe Jun 9 '18 at 14:00
  • \$\begingroup\$ @JayCe heh, my only advantage over you seems to be "going first" as you're quite the golfer! :-) \$\endgroup\$ – Giuseppe Jun 9 '18 at 14:26
13
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ I can do it in 4. Should I spoil it, or do you want to find it by yourself? \$\endgroup\$ – Jakube Sep 14 '17 at 19:48
  • 2
    \$\begingroup\$ @Jakube Wait a tiny bit. Wanna see if I can do it. Is it that obvious? \$\endgroup\$ – Mr. Xcoder Sep 14 '17 at 19:49
  • 1
    \$\begingroup\$ @Jakube Ok, I'll ping when I give up. \$\endgroup\$ – Mr. Xcoder Sep 14 '17 at 19:56
  • 1
    \$\begingroup\$ OsmL or OsmR \$\endgroup\$ – Jakube Sep 14 '17 at 20:23
  • 1
    \$\begingroup\$ @Jakube Ooh that is very clever! Implicit argument d, then maps d over a range...genius! \$\endgroup\$ – Erik the Outgolfer Sep 15 '17 at 10:51
8
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ A so powerful golf for such a simple task. \$\endgroup\$ – Erik the Outgolfer Sep 14 '17 at 18:07
7
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This can be shortened to {bag(@_ Z=>@_).pick} \$\endgroup\$ – Brad Gilbert b2gills Sep 15 '17 at 0:21
  • \$\begingroup\$ @BradGilbertb2gills, sadly that doesn't work. It makes a bag from the pairs (so there would be not "1" once, "2" twice etc., but "1 => 1" once, "2 => 2" also once etc. — not what I want). That's because composers are not coercers, as explained in this Advent Calendar. \$\endgroup\$ – Ramillies Sep 15 '17 at 1:17
  • \$\begingroup\$ @BradGilbertb2gills, but thank you anyway, you helped me to golf out some spaces here and in other challenges too! \$\endgroup\$ – Ramillies Sep 15 '17 at 1:22
  • \$\begingroup\$ I meant {bag(@_ Zxx@_).pick} \$\endgroup\$ – Brad Gilbert b2gills Sep 15 '17 at 16:05
  • \$\begingroup\$ Aah, I see. Why it didn't occur to me... :--) Thanks. \$\endgroup\$ – Ramillies Sep 15 '17 at 17:10
6
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 19 bytes

RandomChoice[#->#]&
\$\endgroup\$
5
\$\begingroup\$

Ruby, 32 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 3, 62 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Could you add an explanation? I'm trying to understand why the for(r*=Math.random();;) is needed, or if all you need is r*=Math.random(). \$\endgroup\$ – Ayb4btu Sep 15 '17 at 19:52
  • \$\begingroup\$ @Ayb4btu Without the for(;;) loop this would require a second (never reached) return statement after the for(int i:a)... to satisfy the compiler - which would be 3 bytes longer. \$\endgroup\$ – Nevay Sep 15 '17 at 20:04
  • \$\begingroup\$ Ah, of course, your for(int i:a) is like a foreach in C#. I had the same problem, but just used a for that continually loops. Your new answer intrigues me, I might try and pilfer some of your ideas. \$\endgroup\$ – Ayb4btu Sep 15 '17 at 20:19
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ ?@+/ is (?@+)/; I'm afraid you'll have to bump that up to 8 again… \$\endgroup\$ – FireFly Sep 16 '17 at 20:48
  • \$\begingroup\$ @FireFly I should've tested it more, good catch. \$\endgroup\$ – cole Sep 16 '17 at 21:23
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I don't think this will have the correct distribution. My tests show that with a=[4,1,5], you'll get about 18% 1, 24% 4, and 58% 5, which suggests you'll get that distribution with any input of length 3. \$\endgroup\$ – Giuseppe Sep 18 '17 at 15:04
  • \$\begingroup\$ That seems correct to me. Higher integer, higher probability. \$\endgroup\$ – kamoroso94 Sep 18 '17 at 15:05
  • \$\begingroup\$ Oh, I see. I misread the question. Excellent solution, +1! \$\endgroup\$ – Giuseppe Sep 18 '17 at 15:07
2
\$\begingroup\$

05AB1E, 9 bytes

εD¸.×}˜.R

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 94 bytes: a=>{int i=-1,r=new Random().Next(a.Sum());for(;r>=0;)r-=a[++i];return a[i];} \$\endgroup\$ – Nevay Sep 15 '17 at 23:50
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

CJam, 5 bytes

lS/mR

Try it online! Note: seperate numbers by a space

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

GolfScript, 17 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 12 bytes

F⪪θ;FIι⊞υι‽υ

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
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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You can sum by using eval(a.join`+`) instead of reduce. \$\endgroup\$ – Justin Mariner Sep 14 '17 at 19:14
  • \$\begingroup\$ If you're ok with ES7+ you can use: [].find(m=>(n-=m)<0,n=Math.random()*eval(a.join+)) and call with input::[].find(...) \$\endgroup\$ – Downgoat Sep 14 '17 at 23:05
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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);. \$\endgroup\$ – Nevay Sep 15 '17 at 14:53
  • \$\begingroup\$ @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 \$\endgroup\$ – Kevin Cruijssen Sep 15 '17 at 15:03
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – Zacharý Sep 15 '17 at 21:05
  • \$\begingroup\$ Wow, I never new <IO> <IO>⍉ to get the main diagonal was even a thing! \$\endgroup\$ – Zacharý Sep 15 '17 at 21:18
  • \$\begingroup\$ @Zacharý Right, thanks. Frankly, I didn't even know about the transpose thing until I tried this task either. Found it here \$\endgroup\$ – Arc676 Sep 16 '17 at 2:39
  • \$\begingroup\$ 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) \$\endgroup\$ – Zacharý Sep 16 '17 at 11:48
  • \$\begingroup\$ @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. \$\endgroup\$ – Arc676 Sep 16 '17 at 11:50
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Really appreciate the explanation, thanks! \$\endgroup\$ – Ian H. Sep 17 '17 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.