18
\$\begingroup\$

Related

You are a manager at a large number factory. You want to show everyone your business is doing well, by showing randomly chosen samples. Unfortunately, your business is not doing that well. But luckily, you have a bit of ingenuity...


Write a program or function that when given an array of unique, positive numbers, which may include floats, returns a random number from the array, with bigger numbers having a higher probability of being chosen \$\left(a_n > a_m \implies P(a_n) > P(a_m)\right)\$, no two numbers being chosen with the same probability \$\left(P(a_n) \not = P(a_m)\right)\$, and all numbers having a non-zero chance of being chosen \$\left(P(a_n) \not = 0\right)\$. Anyways, this is , so shortest code wins!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ I noticed that many (most?) of the answers so far ( including one of mine) only meet the ‘ no two numbers being chosen with the same probability ‘ criterion if the input is restricted to integers. Can you clarify if this is Ok, or otherwise indicate that we should update our (invalid) answers…? \$\endgroup\$ Sep 3, 2023 at 11:41
  • \$\begingroup\$ @DominicvanEssen I believe they're valid. For answers using weights, the numbers 2.7 and 2.7000000001 may look like they do not obey that rule, but in reality they do. The probabilities are extremely close together, but are not equal, so no rules have been broken. \$\endgroup\$ Sep 3, 2023 at 14:19
  • 13
    \$\begingroup\$ I was thinking of answers like my last one that repeat each number in the list a certain (integer) number of times, and then pick one at random. In my case, [1,2,2.7,3] would become [1,2,2,2.7,2.7,3,3,3], so 2 & 2.7 would have the same probaability. I think that the Charcoal, Vyxal, J, Ruby, Factor, and Julia answers all use a variant of this, as well as my (last) R answer. \$\endgroup\$ Sep 3, 2023 at 15:32
  • \$\begingroup\$ Why two close votes? \$\endgroup\$ Sep 6, 2023 at 17:04
  • 3
    \$\begingroup\$ @DominicvanEssen so closing my challenge because of other people's mistakes? \$\endgroup\$ Sep 6, 2023 at 17:17

22 Answers 22

26
\$\begingroup\$

Python, 41 bytes

lambda l:choices(l,l)
from random import*

Attempt This Online! or run it 100000 times

Uses the list itself as the weights.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$ Sep 3, 2023 at 7:12
  • 1
    \$\begingroup\$ @TheEmptyStringPhotographer thanks! Nice challenge btw. \$\endgroup\$
    – MTN
    Sep 3, 2023 at 7:13
  • 2
    \$\begingroup\$ Very good. This one even has a level of plausible deniability ("Oops, I must have misremembered the syntax of choices, sorry"). \$\endgroup\$
    – Emil
    Sep 5, 2023 at 8:54
14
\$\begingroup\$

R, 27 bytes

(Or 20 bytes in R>=4.1 using \ instead of function)

function(x)-sample(-x,1,,x)

Try it online!

The 4th argument of R’s sample function is prob=“a vector of probability weights for obtaining the elements of the vector being sampled”.

Unfortunately, a “convenience” feature of sample changes its behaviour when its first argument is a single positive number, so we need to negate it here to avoid this, and then re-negate the result.

——

R, 31 bytes

(Or 24 bytes in R>=4.1 using \ instead of function)

function(x)max(-sample(-x,2,T))

Try it online!

Return the highest of two random picks.

\$\endgroup\$
11
\$\begingroup\$

Python, 64 bytes (also supports negative numbers)

lambda l:sorted(l)[int(len(l)*random()**.5)]
from random import*

Attempt This Online!

Explanation

Sort the list, the pick a random element. The square root biases the result towards the end of the list.

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

J, 8 bytes

#~{~1?+/

Attempt This Online!

  • 1?+/ Sum the numbers and then choose a random index between 0 and the sum
  • #~{~ Take that index from a new array formed by duplicating each number as many times as itself. Eg, #~ 1 2 3 gives 1 2 2 3 3 3, and we choose a random index from the interval \$[0,6)\$.
\$\endgroup\$
7
\$\begingroup\$

WolframLanguage, 63 48 bytes

Thanks to att for shaving of 15

Sort[#][[Floor@Log2[Random[](2^Tr[1^#]2-3)+2]]]&

Original answer:

f[r_]:=Sort[r][[Floor@Log[2,RandomReal[{2,2^(Length@r+1)-1}]]]]

Sorts the array and picks a random number between 2 and 2^(l+1)-1, where l is the length of the list. Then takes the logarithm to get the array index. This gives each number a twice as high probability to be chosen as the previous one.

Example

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

For a run of 2*10^7 repetitions:

{{1, 19562}, {2, 39068}, {3, 78145}, {4, 156309}, {5, 313362}, {6, 625087}, {7, 1249297}, {8, 2504498}, {9, 5005805}, {10, 10008867}}

enter image description here

\$\endgroup\$
5
  • \$\begingroup\$ An interesting answer. +1 \$\endgroup\$ Sep 3, 2023 at 8:02
  • \$\begingroup\$ [[]] has higher precedence than @ \$\endgroup\$
    – att
    Sep 3, 2023 at 8:03
  • \$\begingroup\$ @att fixed it... \$\endgroup\$ Sep 3, 2023 at 8:07
  • \$\begingroup\$ 48 \$\endgroup\$
    – att
    Sep 3, 2023 at 8:14
  • 2
    \$\begingroup\$ Since the inputs are positive and distinct, how about RandomChoice[#->#]&? \$\endgroup\$ Sep 3, 2023 at 15:52
7
\$\begingroup\$

JavaScript (Node.js), 41 bytes

a=>a.sort()[a.length*Math.random()**.5|0]

Try it online! or run it 100000 times

Takes an Float64Array (so the sorting works properly). Port of bsoelch's Python answer.
+10 bytes to take a regular array.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Wow this even beats the current JavaScript answer! \$\endgroup\$ Sep 3, 2023 at 9:16
  • 2
    \$\begingroup\$ @Arnauld am I allowed to take an Int32Array? Because if I am then we don't need to change the code: Try it online! \$\endgroup\$
    – MTN
    Sep 3, 2023 at 10:48
  • \$\begingroup\$ @MTN my challenge specs just say an array, so an Int32Array might be ok, but in theory it should be able to work for any positive number. \$\endgroup\$ Sep 3, 2023 at 10:50
  • 1
    \$\begingroup\$ Change the first TIO to not use negative numbers, because the sorting doesn't work properly for them. \$\endgroup\$
    – noodle man
    Sep 3, 2023 at 11:11
  • 1
    \$\begingroup\$ @noodleman done, thanks. \$\endgroup\$
    – MTN
    Sep 3, 2023 at 12:48
7
\$\begingroup\$

Vyxal, 4 bytes

℅?℅∴

Try it Online!

Return the highest of two random picks

℅       # Random choice of single item from input array
 ?      # Input (again)
  ℅     # Random choice of single item from this
    ∴   # Maximum of these two values
\$\endgroup\$
8
  • \$\begingroup\$ +1 for your first Vyxal programme! \$\endgroup\$ Sep 3, 2023 at 16:50
  • 1
    \$\begingroup\$ Ayo welcome to Vyxal! Very cool! \$\endgroup\$
    – lyxal
    Sep 3, 2023 at 22:30
  • \$\begingroup\$ Your first solution seems to have a 0 probability to return the smallest element? Am I reading it wrong? \$\endgroup\$
    – ATaco
    Sep 4, 2023 at 6:23
  • \$\begingroup\$ @ATaco - Yes, you're right, I realised that in the car this morning. I'm rolling-back. Oh, well... Thanks for spotting. \$\endgroup\$ Sep 4, 2023 at 7:02
  • \$\begingroup\$ @ATaco - fixed now (I think) \$\endgroup\$ Sep 4, 2023 at 9:24
5
\$\begingroup\$

Ruby, 32 24 bytes

->l{(l+l).sample(2).max}

Try it online!

Thanks to Dominic van Essen for -4 bytes and the idea to get to -8.

\$\endgroup\$
1
  • \$\begingroup\$ 28 bytes porting my 2nd R answer, and works with non-integers... (my first Ruby program...) \$\endgroup\$ Sep 3, 2023 at 15:43
5
\$\begingroup\$

Jelly, 3 bytes

X»X

Attempt This Online!

Distribution over 1000 runs: Attempt This Online!

Uses Dominic van Essen's insight: pick a random element (X), twice, then take the larger of them (»).

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The probability of picking the \$a^{\text{th}}\$ most minor of \$n\$ numbers is \$\frac{2a-1}{n^2}\$. e.g. \$P(3^{\text{rd}}\text{ smallest of }8)=\frac{5}{64}\$. \$\endgroup\$ Sep 4, 2023 at 17:37
4
\$\begingroup\$

JavaScript (Node.js), 58 bytes

a=>a.sort((a,b)=>b-a).filter(_=>Math.random()<.5)[0]||a[0]

Try it online!

Sorts the numbers, filters them randomly, then chooses the largest one.

\$\endgroup\$
2
  • \$\begingroup\$ I don't know JavaScript very well, but this appears to have a possibility of filtering out the empty list? Or is that covered with the a.pop() at the end? \$\endgroup\$ Sep 3, 2023 at 7:27
  • \$\begingroup\$ Yea, it just chooses the largest element if the filtered list is empty. \$\endgroup\$ Sep 3, 2023 at 7:29
4
\$\begingroup\$

Raku, 13 bytes

*.roll(2).max

Attempt This Online!

Picks two elements independently and returns the max of the two.

\$\endgroup\$
1
  • \$\begingroup\$ The probability of picking the \$a^{\text{th}}\$ most minor of \$n\$ numbers is \$\frac{2a-1}{n^2}\$. e.g. \$P(3^{\text{rd}}\text{ smallest of }8)=\frac{5}{64}\$. \$\endgroup\$ Sep 4, 2023 at 17:55
4
\$\begingroup\$

Charcoal, 10 bytes

FAFι⊞υιI‽υ

Try it online! Link is to verbose version of code. Explanation:

FA

Loop over the input numbers.

Fι⊞υι

Push each number that many times to the predefined empty list.

I‽υ

Output a random number from that list.

8 bytes using the newer version of Charcoal on ATO:

I‽ΣEAEιι

Attempt This Online! Link is to verbose version of code. Explanation:

    A       Input list
   E        Map over elements
      ι     Current element
     E      Map over implicit range
       ι    Outer element
  Σ         Flatten
 ‽          Random element
I           Cast to string
            Implicitly print

A port of @JoyalMathew's JavaScript answer in straight succinct Charcoal is only 6 bytes:

I⌈∨Φθ‽

Try it online! Explanation:

    θ   Input list
   Φ    Filtered by
     ‽  Random coin flip
  ∨     If empty then implicitly use input list
 ⌈      Take the maximum
I       Cast to string
        Implicitly print
\$\endgroup\$
2
  • \$\begingroup\$ Do you mean "a port of Joyal Matthew's Javascript answer"...? \$\endgroup\$ Sep 4, 2023 at 5:35
  • \$\begingroup\$ @DominicvanEssen With one "t", but yes, wow, I completely jumped to conclusions there. \$\endgroup\$
    – Neil
    Sep 4, 2023 at 5:50
4
\$\begingroup\$

Wolfram Language (Mathematica), 19 bytes

RandomChoice[#->#]&

Try it online! Like other languages, the builtin can use weights, so the input can serve as the weights as well. Works with nonnegative real numbers.

\$\endgroup\$
3
\$\begingroup\$

Factor, 35 bytes

[ [ dup <array> ] map-flat random ]

Attempt This Online!

Create n copies of each n, and select one at random (uniformly).

For instance, { 5 1 2 } becomes { 5 5 5 5 5 1 2 2 }.

\$\endgroup\$
3
\$\begingroup\$

Julia, 37 bytes

!l=rand([fill.(sort(l),keys(l))...;])

Attempt This Online!

sort the list and repeat each element by their index before randomly choosing a number

with integers only, 25 bytes

!l=rand([fill.(l,l)...;])

Attempt This Online!

directly repeat each number by itself

\$\endgroup\$
3
\$\begingroup\$

Jelly, 4 bytes

ṢxJX

A monadic Link that accepts a list of distinct floats and outputs a random one.

Try it online! Or see the results of 10,000 runs.

How?

Weights by the count of lesser-or-equal values.

The probability of picking the \$a^{\text{th}}\$ most minor of \$n\$ numbers is \$\frac{2a}{n(n+1)}\$.

For example given [2.5, 2.2, 2.4, 2.6, 2.1, 2.3] (\$n(n+1)=6(6+1)=42\$):
$$P(2.1)=\frac{1}{21}, P(2.2)=\frac{2}{21}, \cdots , P(2.6)=\frac{6}{21}$$

ṢxJX - Link: list of numbers, A
Ṣ    - sort {A} -> [a1, a2, a3, ...]
  J  - indices {A} -> [1, 2, 3, ...]
 x   - {sorted A} times {indices of A} -> [a1, a2, a2, a3, a3, a3, ...]
   X - uniform random choice
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 3 bytes

øḊ℅

Try it Online!

Explained

øḊ℅­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌­
øḊ   # ‎⁡Run length decode the input, using the input as both character source and lengths. Basically, zip and run length decode
  ℅  # ‎⁢Choose randomly from that list. 
💎

Created with the help of Luminespire.

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 5 bytes

{.s˜Ω

Try it online.

Or alternatively, a port of @DominicVanEssen's second R answer is 5 bytes as well:

ΩIΩ‚à

Try it online.

Explanation:

{      # Sort the (implicit) input-list from lowest to highest
 .s    # Pop and push a list of its suffixes
   ˜   # Flatten it
    Ω  # Pop and push a random item from this list
       # (which is output implicitly as result)
Ω      # Push a random item from the (implicit) input-list
 I     # Push the input-list
  Ω    # Pop and push another random item from it
   ‚   # Pair the two together
    à  # Pop and push its maximum
       # (which is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

MathGolf, 4 bytes

‼ww╙

Try it online.

Port of @DominicVanEssen's second R answer.

Explanation:

‼     # Apply the next two builtins separately on the current stack:
 w    #  Pop and push a random item from the given (implicit) input-list
  w   #  Same
   ╙  # Pop the top two items on the stack, and leave its maximum
      # (after which the entire stack is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Uiua, 11 bytes

⊡⌊×↥⚂⚂⧻.⊏⍏.

Try it online!

Built on a similar principle to lots of others others (randomly pick two items and use the max), but tweaked slightly

Explanation

        ⊏⍏. # sort the array
      ⧻.    # get its length
   ↥⚂⚂      # max of two random numbers [0,1)
  ×         # multiply to scale to [0,len)
⊡⌊          # floor and index into array
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -pa, 44 bytes

@b=map{($_)x++$,}sort{$a-$b}@F;$_=$b[rand@b]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 47 bytes

a=>a.sort((a,b)=>b-a)[.4/Math.random()|0]||a[0]

Try it online!

JavaScript (V8), 53 bytes

a=>Math.max(...a.map(_=>a[a.length*Math.random()|0]))

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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