Sample integers that sum to one hundred

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.

• 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. May 29 at 19:14
• 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. May 30 at 6:16
• 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)
– ovs
May 30 at 10:13
• 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
May 31 at 4:07
• @xnor aka stars-and-bars. May 31 at 7:34

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]

• Very nice! I wonder if anyone will understand R well enough to copy it into their favourite language :) May 31 at 11:18
• 52 bytes. May 31 at 11:49
• @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... May 31 at 12:08
• @alephalpha this can be 45 bytes and is now a direct translation of your Octave answer. May 31 at 17:05
• It seems that the zeros in the output is always at the end. Jun 1 at 7:34

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.

J, 27 bytes

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


Try it online!

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

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

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

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.

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.

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.

• 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 -↑∘
– ovs
May 31 at 15:46
• {⍵[?⍨≢⍵]}1 0/⍨10,-∘1 can be {100≥?⍨⍵+99} instead.
– ovs
May 31 at 15:49

Python 3.9, 233226224 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.

• Could you explain what it does please. May 30 at 20:24
• You can remove the space between import and *. May 30 at 20:25
• @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. May 30 at 20:27
• Nice solution. TIO? May 30 at 20:50

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

• What are the two values in your input? May 31 at 10:30

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!

• Suggest srand(&n) instead of srand(time(0)) Jun 2 at 15:09

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

• You did, sadly. Jun 16 at 20:51

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

Charcoal, 34 bytes

≔Ｅ⊖Ｎ⁰θ≔Ｅ×χχ¹η⊞υ⁰Ｗ⁺θη⊞υ⎇‽ι⁺⊟υ⊟η⊟θＩυ


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

≔Ｅ⊖Ｎ⁰θ


Create a list of n-1 0s.

≔Ｅ×χχ¹η


Create a list of 100 1s.

⊞υ⁰


Start the output list with one 0 for now.

Ｗ⁺θη


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.

Ｉυ


Output all of the integers.

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.