19
\$\begingroup\$

Given a positive integer n, randomly output n non negative integers that sum to one hundred. n will be at most 200. The output should be present as a list of integers (not sorted).

Your random sample should be uniformly sampled from all lists of n non negative integers that sum to one hundred.

Your code should run in a reasonable amount of time (e.g. should terminate on TIO) for n less than a 200 . This is just to prevent brute force solutions.

Examples

If n=1 the code should always output 100

If n=2 the code should output 100,0 or 99,1 or 98,2 or 97,3 ... or 2,98 or 1,99 or 0,100 with equal probability. There are 101 different possible outputs in this case.

If n>100 then some of the values in the output will necessarily be 0.

\$\endgroup\$
9
  • 4
    \$\begingroup\$ This is an interesting challenge but could do with with a bit more thought. It would have benefited from posting in the sandbox (see panel at top right of your screen) What is the possible range of n?` if n=1 the output would be just 100, if n=2 it would be 2 numbers. Up to n=100, or n=1000 where most of the ouput list will be zeroes. Should output be presented as an unordered list, or sorted? Some examples would be useful. \$\endgroup\$ May 29 at 19:14
  • 7
    \$\begingroup\$ related != duplicate, @graffe. It is a cultural quirk of this site to often post related questions in the comments of questions. It can often be useful to challenge-seekers that like a particular challenge and would like to see more of the same ilk. \$\endgroup\$ May 30 at 6:16
  • 5
    \$\begingroup\$ With requiring a uniform distribution and preventing bruteforce it is definitely a hard challenge, but that shouldn't be a reason for downvotes. Some people generally dislike banning specific approaches, maybe thats it. (I personally think this will become less interesting if you allow it) \$\endgroup\$
    – ovs
    May 30 at 10:13
  • 12
    \$\begingroup\$ It doesn't look like anyone has done this yet, but a slick approach is to make a list of 100 ones and n-1 zeros, shuffle it, and list off the lengths of the n runs of ones separated by zeroes. \$\endgroup\$
    – xnor
    May 31 at 4:07
  • 3
    \$\begingroup\$ @xnor aka stars-and-bars. \$\endgroup\$ May 31 at 7:34

15 Answers 15

8
\$\begingroup\$

R, 64 bytes

\(n,m=rle(c(1,sample(!c(1:99,!1:n-1)),1)))c(m$l[!m$v],!1:n)[1:n]

Attempt This Online!

Implementation of 'sticks-and-stones' as suggested by xnor.

Ungolfed

function(n){
    w=rep(0:1,times=c(n-1,100)) # n-1 zeros, followed by 100 ones
    x=sample(w)                 # randomly shuffle it
    y=c(0,x,0)                  # and add zeros at the start & the end
    m=rle(y)                    # get the lengths of runs of 1s and 0s
    o=m$lengths[m$values==1]    # lengths of the runs of ones
    p=m$lengths[m$values==0]-1  # lengths of the runs of zeros, minus 1
    q=sum(p)                    # so q is the number of zero-length runs of 1s
    z=rep(0,q)                  # repeat zero that many times
    return(c(o,z))              # and return the concatenation of the runlengths of 1s and the zero-length runs
}

Golfing tricks
rep(0:1,times=c(n-1,100)) -> !c(1:99,!1:n-1)
c(m$lengths[m$values==1],rep(0,sum(m$lengths[m$values==0]-1))) -> c(m$l[!m$v],!1:n)[1:n]

\$\endgroup\$
7
  • \$\begingroup\$ Very nice! I wonder if anyone will understand R well enough to copy it into their favourite language :) \$\endgroup\$
    – graffe
    May 31 at 11:18
  • 4
    \$\begingroup\$ 52 bytes. \$\endgroup\$
    – alephalpha
    May 31 at 11:49
  • 2
    \$\begingroup\$ @alephalpha - That can even be 49 bytes with some R-specific golfing, but I think you should post it yourself as it's a significant change of approach... \$\endgroup\$ May 31 at 12:08
  • 3
    \$\begingroup\$ @alephalpha this can be 45 bytes and is now a direct translation of your Octave answer. \$\endgroup\$
    – Giuseppe
    May 31 at 17:05
  • \$\begingroup\$ It seems that the zeros in the output is always at the end. \$\endgroup\$
    – alephalpha
    Jun 1 at 7:34
6
\$\begingroup\$

Octave, 46 bytes

@(n)diff([0,sort(randperm(n+99,n-1)),n+100])-1

Try it online!

Based on @xnor's comment. But instead of shuffling a list of zeros and ones, here I generate a random permutation of 1:n+99, and see the first n-1 terms as the positions of zeros.

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

J, 27 bytes

0+/;.1@,1 0({~#?#)@#~100,<:

Try it online!

Sticks and stones method thanks to xnor's idea from the comments.

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

Pyth, 16 bytes

lMc.S+*100N*tQdd

Try it online!

Based on xnor's comment.

  • *100N: 100 " characters
  • *tQd: n-1 space characters
  • .S+: Concatenate, shuffle
  • c ... d: Split on spaces
  • lM: Map to lengths of remaining pieces
\$\endgroup\$
3
\$\begingroup\$

Desmos, 77 bytes

l=[2...n]
L=join(0,[1...99+n].shuffle[l[l0+n>1]].sort,100+n)
f(n)=L[2...]-L-1

Uses xnor's Stars and Bars idea.

Try It On Desmos!

Try It On Desmos! - Prettified

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

PARI/GP, 82 bytes

n->Vec(Ser(concat([Set(numtoperm(m=n+99,random(m!))[1..n-1]),m+1]))*(y=1-x)-1/y,n)

Attempt This Online!

Based on @xnor's comment:

It doesn't look like anyone has done this yet, but a slick approach is to make a list of 100 ones and n-1 zeros, shuffle it, and list off the lengths of the n runs of ones separated by zeroes. – xnor

PARI/GP doesn't have a built-in for shuffling, but we can generate a random permutation of [1..n+100-1] using numtoperm and random, and see the first n-1 terms as the positions of zeros.


PARI/GP, 94 bytes

n->b=binomial;r=random(b(n+99,k=100));[while(r>=s=b(n-l+k-1,k),r-=s;i++;k--)+i|l<-[1..n],!i=0]

Attempt This Online!

The number of possible outputs is binomial(n+100-1,100). Here I first generate a random number r in the range [0..binomial(n+100-1,100)-1], and then find the rth result. So this is guaranteed to be uniform.

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

Python 3, 88 bytes

lambda n:[*map(len,bytes(sample([0]*100+[9]*~-n,n+99)).split(b'	'))]
from random import*

Try it online!

Also uses the "sticks and stones" method.

This creates a list of 100 0s and n−1 9s, then sample gives n+99 elements (which is all of them) in a random order. The result is then converted to bytes in order to use split; 9 was chosen because it corresponds to the tab character (which is placed in the bytes literal for the argument to split). Finally, use map to take the length of each piece, and [*…] makes it into a list.

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

APL(Dyalog Unicode), 28 bytes SBCS

-↑∘{+/¨⍵⊂⍨1@1~⍵}{100≥?⍨⍵+99}

Try it on APLgolf!

A train which takes a single integer. Uses the sticks and stones method, since it translates quite well to APL.

-6 from ovs.

\$\endgroup\$
2
  • \$\begingroup\$ This fails (by producing one to few values) if ~b already has a 1 at the first index. I think this can be fixed by prepending -↑∘ \$\endgroup\$
    – ovs
    May 31 at 15:46
  • \$\begingroup\$ {⍵[?⍨≢⍵]}1 0/⍨10,-∘1 can be {100≥?⍨⍵+99} instead. \$\endgroup\$
    – ovs
    May 31 at 15:49
1
\$\begingroup\$

Python 3.9, 233 226 224 211 Bytes

import random
from functools import*
r,p=range,cache(lambda n,s:s<1 if n<1 else sum(p(n-1,k)for k in r(s+1)))
def f(n,s):
    k=random.choices(r(s+1),[p(n-1,k)for k in r(s+1)])[0]
    return[]if n<1 else[s-k]+f(n-1,k)

TIO link. Slightly longer as the cache decorator is only available in Python 3.9.

\$\endgroup\$
4
  • \$\begingroup\$ Could you explain what it does please. \$\endgroup\$
    – graffe
    May 30 at 20:24
  • \$\begingroup\$ You can remove the space between import and *. \$\endgroup\$ May 30 at 20:25
  • 2
    \$\begingroup\$ @graffe It counts the number of solutions with each possible first number, and uses the counts as weights to select the first number, then recursively samples the rest of the list. \$\endgroup\$ May 30 at 20:27
  • \$\begingroup\$ Nice solution. TIO? \$\endgroup\$
    – graffe
    May 30 at 20:50
1
\$\begingroup\$

Burlesque, 49 bytes

s10 100rn1bx100.*FL{jg_x/0x/ia}{g1-.Js1}w!q0;;)++

Try it online!

Inputs are random seed and count.

s1         # Save count
0 100rn    # Random numbers 0..100 (seeded by second input)
1bx100.*FL # 100 1s
{    
  j        # Reorder stack
  g_       # Get head of random number
  x/0x/ia  # Insert a 0 at that position
 }{
  g1-.Js1  # Decrement count and check
 }w!       # While
 q0;;      # Split on 0s
 )++       # Sum each block
\$\endgroup\$
1
  • \$\begingroup\$ What are the two values in your input? \$\endgroup\$
    – graffe
    May 31 at 10:30
1
\$\begingroup\$

C (clang), 125 bytes

i=99,j,a[300];main(n){scanf("%d",&n);n+=i;for(srand(time(0));~i;)a[rand()%n]++||--i;for(;i<n;)j=a[++i]?j+1:!printf("%d ",j);}

An implementation of xnor's suggestion in C.

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Suggest srand(&n) instead of srand(time(0)) \$\endgroup\$
    – ceilingcat
    Jun 2 at 15:09
1
\$\begingroup\$

Wolfram Language (Mathematica), 41 bytes

Edit: I have made my code much simpler and shorter.

Values[Counts[RandomInteger[{1,#},100]]]&

RandomInteger creates a random number between 1 and the given input integer, with uniform probability. This is done 100 times, and Counts tallies up the number of appearances of each number.

Try it online!

Old code from my previous submission is below.

Length/@Select[Flatten[Split[RandomChoice[Join[Riffle[Table[1,{#}]&/@#,0]]&/@Flatten[Permutations/@IntegerPartitions[100+#,{#}]-1,1]]],1],Length[#]>1&]&
\$\endgroup\$
1
  • \$\begingroup\$ You did, sadly. \$\endgroup\$
    – graffe
    Jun 16 at 20:51
1
\$\begingroup\$

JavaScript (Node.js), 94 bytes

f=(n,s=100,g=Math.random,i=g()*-~s|0)=>--n?g()*s**n<(i+1)**n-i**n?[...f(n,i),s-i]:f(n+1,s):[s]

Try it online!

Probable ret[0]==s-i is ((i+1)**n-i**n)/s**n

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

Charcoal, 34 bytes

≔E⊖N⁰θ≔E×χχ¹η⊞υ⁰W⁺θη⊞υ⎇‽ι⁺⊟υ⊟η⊟θIυ

Try it online! Link is to verbose version of code. Explanation: Uses @xnor's method.

≔E⊖N⁰θ

Create a list of n-1 0s.

≔E×χχ¹η

Create a list of 100 1s.

⊞υ⁰

Start the output list with one 0 for now.

W⁺θη

Repeat until all of the 0s and 1s have been popped.

⊞υ⎇‽ι⁺⊟υ⊟η⊟θ

Select one of them at random. If it's a 1, then increment the latest number in the output list, otherwise push one of the 0s to the output list, all while removing the 1 or 0 from its list as appropriate.

Iυ

Output all of the integers.

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

Retina, 43 bytes

.+
*
_$
100*@¶
+@v`(.)(.*¶)
$2$1
¶

S`_
%`@

Try it online! Explanation:

.+
*

Convert to unary (using _).

_$
100*@¶

Decrement the input, append 100 @s, and create a work area for the shuffle.

+@v`(.)(.*¶)
$2$1

Repeatedly select a character randomly from the first line and move it to the start of the second line. (The + indicates to repeat, the @ selects randomly, and the v allows the matches to overlap, which doesn't matter here since we're only replacing one at a time.)

Delete the input area.

S`_

Split the working area on _s. Since there were n-1 of them, there are now n lines.

%`@

Count the number of @s on each line.

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