Be big more often

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!

• 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…? Commented Sep 3, 2023 at 11:41
• @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. Commented Sep 3, 2023 at 14:19
• 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. Commented Sep 3, 2023 at 15:32
• Why two close votes? Commented Sep 6, 2023 at 17:04
• @DominicvanEssen so closing my challenge because of other people's mistakes? Commented Sep 6, 2023 at 17:17

Python, 41 bytes

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


Uses the list itself as the weights.

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

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.

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.

• Interesting solution! +1 Commented Sep 3, 2023 at 8:32

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

WolframLanguage, 63 48 bytes

Thanks to att for shaving of 15

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


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

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

JavaScript (Node.js), 41 bytes

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


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

• Wow this even beats the current JavaScript answer! Commented Sep 3, 2023 at 9:16
• @Arnauld am I allowed to take an Int32Array? Because if I am then we don't need to change the code: Try it online!
– MTN
Commented Sep 3, 2023 at 10:48
• @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. Commented Sep 3, 2023 at 10:50
• Change the first TIO to not use negative numbers, because the sorting doesn't work properly for them. Commented Sep 3, 2023 at 11:11
• @noodleman done, thanks.
– MTN
Commented Sep 3, 2023 at 12:48

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

• +1 for your first Vyxal programme! Commented Sep 3, 2023 at 16:50
• Ayo welcome to Vyxal! Very cool! Commented Sep 3, 2023 at 22:30
• Your first solution seems to have a 0 probability to return the smallest element? Am I reading it wrong? Commented Sep 4, 2023 at 6:23
• @ATaco - Yes, you're right, I realised that in the car this morning. I'm rolling-back. Oh, well... Thanks for spotting. Commented Sep 4, 2023 at 7:02
• @ATaco - fixed now (I think) Commented Sep 4, 2023 at 9:24

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.

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

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

• 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}$. Commented Sep 4, 2023 at 17:37

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.

• 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? Commented Sep 3, 2023 at 7:27
• Yea, it just chooses the largest element if the filtered list is empty. Commented Sep 3, 2023 at 7:29

Raku, 13 bytes

*.roll(2).max


Attempt This Online!

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

• 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}$. Commented Sep 4, 2023 at 17:55

Charcoal, 10 bytes

ＦＡＦι⊞υιＩ‽υ


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

ＦＡ


Loop over the input numbers.

Ｆι⊞υι


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

Ｉ‽υ


Output a random number from that list.

8 bytes using the newer version of Charcoal on ATO:

Ｉ‽ΣＥＡＥιι


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

    Ａ       Input list
Ｅ        Map over elements
ι     Current element
Ｅ      Map over implicit range
ι    Outer element
Σ         Flatten
‽          Random element
Ｉ           Cast to string
Implicitly print


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

Ｉ⌈∨Φθ‽


Try it online! Explanation:

    θ   Input list
Φ    Filtered by
‽  Random coin flip
∨     If empty then implicitly use input list
⌈      Take the maximum
Ｉ       Cast to string
Implicitly print

• Do you mean "a port of Joyal Matthew's Javascript answer"...? Commented Sep 4, 2023 at 5:35
• @DominicvanEssen With one "t", but yes, wow, I completely jumped to conclusions there.
– Neil
Commented Sep 4, 2023 at 5:50

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.

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

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

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


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.

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)


MathGolf, 4 bytes

‼ww╙


Try it online.

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)


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


Perl 5-pa, 44 bytes

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


Try it online!

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!