Sample integers that sum to one hundred

Question

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.

Answer 1

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]

Answer 2

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.

Answer 3

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

Answer 4

J, 27 bytes

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

Try it online!

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

Answer 5

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

Answer 6

C (clang), 125 120 115 bytes

• -5 bytes thanks to @ceilingcat

i=99,j,a[];main(n){scanf("%d",&n);n+=i;for(srand(&n);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!

Answer 7

05AB1E, 9 bytes

т∍ú¦.r#€g

Inspired by @isaacg's Pyth answer, using @xnor's approach.

Try it online or verify a few random outputs at once.

Explanation:

 ∍         # Extend the (implicit) input
т          # to length 100
           # (resulting in a string - e.g. n=50 becomes "505050...50")
  ú        # Pad this string with the (implicit) input amount of leading spaces
           # (it's important to note that `∍` results in a string instead of integer,
           # otherwise this would have resulted in "50" with 505050...50 amount of
           # leading spaces instead)
   ¦       # Remove the first space, so there are input-1 amount of spaces
    .r     # Randomly shuffle the characters in this string
      #    # Split it on spaces
       €g  # Get the length of each inner string
           # (after which the result is output implicitly)

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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

Answer 13

JavaScript (Node.js), 99 bytes

f=(n,a=[100])=>--n?f(n,a.flatMap(v=>(s||s++)<p&&(s+=v)>p?[d=s-p|0,v-d]:v,p=Math.random(s=0)*101)):a

Attempt This Online!

A recursive approach that starts with the array [100], and 'splits' it randomly n times.
eg. [27, 51, 22] -> [27, 11, 40, 22]

The hardest (and most costly) part is making sure [0, 100] is a possible output.

There is an extremely slim chance (at most approx. 1 in 2⁵³, source) of the function producing invalid output, when Math.random() returns exactly 0.

Answer 14

GolfScript, 42 bytes

100\(:a+,{;9.?rand}${a<}%1+{.1?.@@)>n\.}do

Try it online!

For some reason I just had to use GolfScript for this. No idea why though, I've never used this language before. Anyways, this is yet another implementation of xnor's idea.

100         # push 100 onto the stack   
\(:a        # store n-1 in variable a
+,          # create array of ints from 0 to (100 + n-1) - 1
{;9.?rand}$ # shuffle array, method taken from GS tips page
{a<}%       # map items to 0 if they are >=a and to 1 if they are <1
1+          # append 1 to list. 
            # This is done so that ? always finds a 1 later
{
  .1?       # find position of first 1 in array
  .@@       # move a copy of that position to the back of the stack
  )>        # discard all elements with an index < (position - 1)
  n\        # push a newline onto the stack, flip array back to the top
            # The implicit output concats all stack values together :(
.}do        # repeat until array is empty

The program expects n to be at to top of the stack. TIO's input field does ...unexpected things, so the header field is used to provide input instead.

Answer 15

Vyxal W, 13 bytes

‹(₁ʀ℅)₁Ws₍h¯f

choose cut positions and sort them, append 100 at the end, calculate the difference

=>first number, differences...

Try it Online!

Answer 16

Ly, 22 bytes

'dspn,[r0l?:lf-spr,]pl

Try it online!

This meets the requirements in that all possible combinations of numbers that sum to 100 could be returned, but I don't think all of them have an equal chance. But someone with better understanding of statistics would have to weigh in to be sure... If that's a disqualification, I'll remove the answer. But from what I can tell, the approach is different from the other algorithms used so it might be interesting?

At a high level, the code loops N-1 times where N is the count requested on STDIN. Each time through the loop it generates a random number in 0-X where X starts at 100 and is decremented by the number added to the list each time. Once the loop is exhausted, it finds the number requires to get the sum to 100 and uses that as the last entry.

'dsp                   - Load "100", save to backup cell and pop from stack
    n,                 - Read list size "N" requested from STDIN, decrement
      [r         r,]p  - Loop once for "N-1" times
        0l?            - Load backup cell, generate random number in "0-X"
           :           - Duplicate random pick
            lf-        - Sub random pick from previous "left to sum" number
               sp      - Save new "left to sum" to backup cell and pop from stack
                     l - Load "left to sum" from backup cell
                       - Stack prints as numbers by default on exit

Answer 17

Setanta, 125 bytes

gniomh(n){s:="1"*100le i idir(0,n-1){i=randUimh@mata(0,101+i)s=cuid@s(0,i)+"0"+cuid@s(i,fad@s)}toradh thar(fad,roinn@s("0"))}

try-setanta.ie link

Answer 18

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.

Answer 19

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

Answer 20

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.

Answer 21

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

Answer 22

Japt, 13 bytes

î ÅiLî¬ ö¬¸mÊ

Try it