9
\$\begingroup\$

Given an integer n >= 1 as input, output a sample from the discrete triangular distribution over the integers k, for 1 <= k <= n (1 <= k < n is also acceptable), defined by p(k) ∝ k.

E.g. if n = 3, then p(1) = 1/6, p(2) = 2/6, and p(3) = 3/6.

Your code should take constant expected time, but you are allowed to ignore overflow, to treat floating point operations as exact, and to use a PRNG (pseudorandom number generator).

You can treat your random number generator and all standard operations as constant time.

This is code golf, so the shortest answer wins.

\$\endgroup\$
3
  • 9
    \$\begingroup\$ An explanation of the discrete triangular distribution with some test cases would be a lot clearer. Also reasonable quality isn't an objective criteria. \$\endgroup\$
    – Noodle9
    Oct 4, 2022 at 11:42
  • 1
    \$\begingroup\$ I suggest you remove the "reasonable quality" requirement for the PRNG. We usually assume that PRNG's are good enough; see for example here \$\endgroup\$
    – Luis Mendo
    Oct 4, 2022 at 12:22
  • 3
    \$\begingroup\$ Perhaps you should also explain what you intend by "your code should take constant expected time". Currently, answers seem to make different assumptions about whether a PRNG can be expected to run in constant time for all values of n in random_function(n), or whether this matters. \$\endgroup\$ Oct 4, 2022 at 13:30

9 Answers 9

6
\$\begingroup\$

JavaScript (ES7), 37 bytes

-1 thanks to @Neil

n=>(Math.random()*n*-~n+1|0)**.5+.5|0

Try it online!

How?

We essentially pick a random integer in \$\left[1\dots\sum_{k=1}^{n}k\right]\$ and then return the corresponding term in the sequence \$1,2,2,3,3,3,4,4,4,4,\dots\$ (this is A002024).

A more readable form of the formula is:

$$\left\lfloor\sqrt{2 \times\left\lfloor \operatorname{rand}()\times {n+1\choose 2}+1 \right\rfloor }+1/2\right\rfloor$$

leading to:

$$\left\lfloor\sqrt{2 \times\lfloor \operatorname{rand}()\times n\times(n+1)/2+1 \rfloor }+1/2\right\rfloor$$

where \$\operatorname{rand}()\$ is assumed to return a random value drawn from the uniform distribution in the interval \$[0,1[\$.

\$\endgroup\$
3
  • \$\begingroup\$ n=>(Math.random()*n*-~n+1)**.5+.5|0 avoids the second floor. \$\endgroup\$
    – Neil
    Oct 4, 2022 at 15:55
  • \$\begingroup\$ @Neil This may occasionally return n+1. \$\endgroup\$
    – Arnauld
    Oct 4, 2022 at 18:34
  • 1
    \$\begingroup\$ My bad, but at least +1 allows you to use |0 instead of &-1. \$\endgroup\$
    – Neil
    Oct 4, 2022 at 22:06
5
\$\begingroup\$

Python, 57 bytes

lambda n:max(r(1,n),r(n))
from random import*
r=randrange

Attempt This Online!

Python, 60 bytes

lambda n:max(divmod(randrange(n,n*n),n))
from random import*

Attempt This Online!

Picture:

   |  0  1  2  3  4  5
---+------------------
1  |  1  1  2  3  4  5
2  |  2  2  2  3  4  5
3  |  3  3  3  3  4  5
4  |  4  4  4  4  4  5
5  |  5  5  5  5  5  5
\$\endgroup\$
3
\$\begingroup\$

R, 46 bytes

function(n)((1+4*runif(1)*n*(n+1))^.5-1)%/%2+1

Try it online!

runif(1) calculates a random number from the uniform distribution from zero to one. We then need to work-out which triangularly-increasing interval this lies in. So we multiply by the size of the full triangle (n*(n+1)/2) to get c, and solve the quadratic equation x(x+1)/2=c = x^2+x-2*c=0 (using the quadratic formula) to get the answer x.

\$\endgroup\$
4
  • \$\begingroup\$ The question is a little unclear, but shouldn't sample(n,1,,1:n) work? \$\endgroup\$
    – Giuseppe
    Oct 4, 2022 at 12:04
  • \$\begingroup\$ @Giuseppe - That was my original (now-deleted) answer, but it doesn't run in constant expected time. It takes much longer to run for large values of n, presumably due to the extra work of weighted sampling from bigger-and-bigger vectors... \$\endgroup\$ Oct 4, 2022 at 12:06
  • \$\begingroup\$ @Giuseppe - try it \$\endgroup\$ Oct 4, 2022 at 12:08
  • \$\begingroup\$ ah, I didn't test that. Good catch! \$\endgroup\$
    – Giuseppe
    Oct 4, 2022 at 12:35
3
\$\begingroup\$

Python, 71 bytes

lambda x:x-abs((a:=r(x)-r(x+1))+(a>=0))
from random import*
r=randrange

Attempt This Online!

Surprisingly tricky. Uses the fact that the sum of 2 numbers form a rectangle, then using a>=0 to add 1 to negative numbers then abs merges both halves of the triangle.

\$\endgroup\$
1
  • \$\begingroup\$ It seems like your explanation is out of date? \$\endgroup\$ Oct 4, 2022 at 13:16
3
\$\begingroup\$

Vyxal, 7 6 bytes

-1 thanks to @emanresu A

›℅‹$℅x

Try it Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The : is unnecessary \$\endgroup\$
    – emanresu A
    Jan 28 at 1:48
2
\$\begingroup\$

Charcoal, 14 bytes

I⌊⁺·⁵₂⊕‽X⁺·⁵N²

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

            N   Input `n` as a number
         ⁺·⁵    Plus literal number `0.5`
        X    ²  Squared
       ‽        Random element of implicit range
      ⊕         Incremented
    ₂           Square root
  ⁺·⁵           Plus literal number `0.5`
 ⌊              Floor
I               Cast to string
                Implicitly print

Example: For n=4, the implicit range is [0..20), which the remaining code maps 0..1 to 1, 2..5 to 2, 6..11 to 3 and 12..19 to 4, thus p(k)∝k as desired.

\$\endgroup\$
4
  • \$\begingroup\$ Neil - does sampling from a range execute in constant time in Charcoal for all range sizes? In R, for instance, it's slower to sample from a big range than from a small one... try it in R \$\endgroup\$ Oct 4, 2022 at 12:19
  • \$\begingroup\$ @DominicvanEssen Certainly Charcoal calls the underlying API in constant time... \$\endgroup\$
    – Neil
    Oct 4, 2022 at 13:00
  • \$\begingroup\$ I also tried to port your approach, and I'm having difficulty (but maybe I just don't understand the explanation...). You explain: "12..19 maps to 4", but I calculate that floor(sqrt(12 + 1.5)) is equal to 3. \$\endgroup\$ Oct 4, 2022 at 13:19
  • 1
    \$\begingroup\$ @DominicvanEssen Whoops, somehow I conflated the floor(sqrt(12+1)+0.5) into a floor(sqrt(12+1.5))... fixed now. \$\endgroup\$
    – Neil
    Oct 4, 2022 at 15:49
1
\$\begingroup\$

C (gcc), 43 bytes

f(n){n=sqrt(2*(rand()/21e8*n*++n/2)+1)-.5;}

Try it online!

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

Pyt, 9 bytes

Đř⇹0⇹Ř×ʀ↑

Try it online!

Port of @loopy walt's answer

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

Raku, 24 bytes

{Bag(1..*Z=>1..$_).pick}

Try it online!

A Bag object is a set with multiplicity, and it has a pick method that returns a random key, where each key is weighted by its multiplicity in the bag. Here it's initialized with a list of the numbers from 1 up to the input argument $_, each one weighted by itself.

  • 1 .. * is the infinite list of natural numbers.
  • 1 .. $_ is the list of natural numbers from 1 up to the input argument.
  • Z=> zips those two lists together with the pair creation operator =>. It stops when it reaches the end of the shorter/noninfinite list, of course.
\$\endgroup\$

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.