21
\$\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\$
10
  • 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\$ Commented May 29, 2022 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\$
    – Qaziquza
    Commented May 30, 2022 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
    Commented May 30, 2022 at 10:13
  • 15
    \$\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
    Commented May 31, 2022 at 4:07
  • 3
    \$\begingroup\$ @xnor aka stars-and-bars. \$\endgroup\$ Commented May 31, 2022 at 7:34

21 Answers 21

7
\$\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\$
    – user108721
    Commented May 31, 2022 at 11:18
  • 4
    \$\begingroup\$ 52 bytes. \$\endgroup\$
    – alephalpha
    Commented May 31, 2022 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\$ Commented May 31, 2022 at 12:08
  • 3
    \$\begingroup\$ @alephalpha this can be 45 bytes and is now a direct translation of your Octave answer. \$\endgroup\$
    – Giuseppe
    Commented May 31, 2022 at 17:05
  • \$\begingroup\$ It seems that the zeros in the output is always at the end. \$\endgroup\$
    – alephalpha
    Commented Jun 1, 2022 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\$

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

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

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!

\$\endgroup\$
1
  • \$\begingroup\$ 116 bytes \$\endgroup\$
    – jdt
    Commented Sep 23, 2022 at 13:08
2
\$\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\$

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)
\$\endgroup\$
1
\$\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\$
1
\$\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\$
1
\$\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
    Commented May 31, 2022 at 15:46
  • \$\begingroup\$ {⍵[?⍨≢⍵]}1 0/⍨10,-∘1 can be {100≥?⍨⍵+99} instead. \$\endgroup\$
    – ovs
    Commented May 31, 2022 at 15:49
1
\$\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\$
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\$ I think the count is not uniformly distributed, if you want to get a 0 in n=2, it means (1/2)^100 instead of 1/101 \$\endgroup\$
    – okie
    Commented Sep 24, 2022 at 5:29
1
\$\begingroup\$

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 253, source) of the function producing invalid output, when Math.random() returns exactly 0.

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

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.

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

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!

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

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
\$\endgroup\$
0
\$\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\$
    – user108721
    Commented May 30, 2022 at 20:24
  • \$\begingroup\$ You can remove the space between import and *. \$\endgroup\$ Commented May 30, 2022 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\$ Commented May 30, 2022 at 20:27
  • \$\begingroup\$ Nice solution. TIO? \$\endgroup\$
    – user108721
    Commented May 30, 2022 at 20:50
0
\$\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\$
    – user108721
    Commented May 31, 2022 at 10:30
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\$

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

Japt, 13 bytes

î ÅiLî¬ ö¬¸mÊ

Try it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.