Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Write an algorithm in any programming language you desire that generates n unique randomly-distributed random natural numbers (i.e. positive integers, no zero), sum of which is equal to t, where t is bigger than or equal to n*(n+1)/2.

Example: Generate 10 unique random natural numbers, sum of which is equal to 500.


migration rejected from Jul 11 '14 at 17:57

This question came from our site for professional and enthusiast programmers. Votes, comments, and answers are locked due to the question being closed here, but it may be eligible for editing and reopening on the site where it originated.

closed as off-topic by user80551, Ventero, Peter Taylor, Kyle Kanos, ProgramFOX Jul 11 '14 at 17:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – user80551, Ventero, Peter Taylor, Kyle Kanos, ProgramFOX
If this question can be reworded to fit the rules in the help center, please edit the question.

What random distribution? Even distribution over the naturals isn't possible. – Aaron Dufour Oct 3 '12 at 2:21
What's the winning criterion? – grc Oct 3 '12 at 3:19
+1 Nice question and interesting to solve. – DavidC Oct 3 '12 at 13:22
It isn't clear to me what "randomly distributed" means here. Do you mean "uniformly distributed over the set of possible outputs"? Or something weaker? – Keith Randall Oct 3 '12 at 16:11
If the sum has to be a set value, these sampled numbers can't be independent of one another... – airza Oct 4 '12 at 14:51


This truly (up to RNG quality) gives a uniform random choice over the set of all such partitions.

import random
def parts(n,t,b=None):
    if b is None:
        b = n
    if t == 1:
        if n<b:
            yield [n]
    for i in range(1,min(b,n)):
        for s in parts(n-i,t-1,i):
            yield s+[i]
def random_part(n,t):
    S = list(part(n,t))
    return random.choice(S)

Of course, this won't work if it fills up the memory...

Hehehe, basically doing random.choice(all_possible_solutions) – beary605 Oct 5 '12 at 0:23
@beary605 replace "basically" and "precisely" and I'll agree with you. Uniform generation of combinatorial objects like this is notoriously hard, typically requiring elaborate constructions and Boltzmann sampling. See, for example. – boothby Oct 5 '12 at 5:33
ugh, sorry for the non-free reference. I believe it's covered in Flajolet and Sedgewick's Analytic Combinatorics (a free download), but is currently unresponsive and I can't check. – boothby Oct 5 '12 at 5:40

Python, 155, 149

from random import*;x=input();n=x[0];a=[1+i for i in range(n)]
while sum(a)<x[1]:i=randint(n-x[1]+sum(a),n);a=[j+(a.index(j)>=i)for j in a]
print a

Takes input of the form [n,t]


Start with the the range 1,2...n with a sum of n(n+1)/2. Then select an index i such that adding 1 to each element of index >= i will not produce a sum > n. Repeat until sum is reached.

No golf tag on this one. – Steven Rumbalski Oct 4 '12 at 14:58


Input is given as [n, t]

Note that these solutions are extremely slow ;)


import random
while sum(a)!=b[1] and len(set(a))!=b[0]:
    a=[random.randint(1, b[1])for i in xrange(b[0])]
print a

Golfed (108 chars):

import random
while [sum(c),len(set(c))]!=b:random.shuffle(a);c=a[:b[0]]
print a

I'll work on a faster version when I have time.

This does not generate unique numbers. – scleaver Oct 3 '12 at 17:24
@scleaver: fixed it. len(set(a))==b[0] – beary605 Oct 3 '12 at 23:33


Takes input from the variables n and t

from itertools import combinations
from random import shuffle
r = range(t)
for x in combinations(r, n):
  if sum(x)==t:
    print x

This solution is very slow. For the test case of n, t = 5, 500, it took almost 11 seconds to complete. The numbers aren't guaranteed to be uniformly distributed, but each solution is equally likely to be found.




A While loop was added to avoid zero as well as repeated random numbers.


g[n_, partitions_] := 
 Module[{f, x}, 
  f[n1_, p1_] := 
   Sort[Length /@ (IntegerDigits /@ 
         StringInsert[StringJoin@ConstantArray["1", n], "\n", 
          RandomSample[2~Range~n, p1 - 1]], "Data"])]; 
  x = f[n, partitions];
  While[Length[DeleteDuplicates[Complement[x, {0}]]] != partitions, 
   x = f[n, partitions]]; RandomSample[x]]


g[500, 10]

{51, 102, 94, 5, 64, 1, 131, 25, 3, 24}




RandomSample[Range[2, total], parts - 1] selects n-1 positions for partitioning the set.

StringInsert[StringJoin@ConstantArray["1", total], "\n", %] inserts n-1 newlines into a list containing total elements (each of which is a 1). The newlines are placed in the positions obtained just above.

Flatten@ImportString[%, "Data"] separates the sublists as numbers containing 1's.

Length /@ (IntegerDigits /@ f) // Sort counts the 1's in each sublist.

Somehow, we both missed the word "unique" in the problem... – boothby Oct 3 '12 at 6:22
@boothby Good catch. I have now fixed it. – DavidC Oct 3 '12 at 13:26


Using the algorithm supplied in this Stack Overflow answer reproduced below:

Generate N-1 random numbers between 0 and 1, add the numbers 0 and 1 themselves to the list, sort them, and take the differences of adjacent numbers.

For our case, the range is 1 to sum and we'll be inserting 0 and sum into the list. As @HamidNazari points out, we can't assume that the array will be unique after taking the differences, so we'll have to check for that, too.

Quick and dirty implementation in Ruby:

def rand_sum(size, sum)
  rand_set = []
  rand_set |= [rand(1...sum)] until rand_set.size == size - 1
  rand_set << 0 << sum
  rand_set = rand_set.sort.each_cons(2).map { |x, y| y - x }.uniq
  return rand_set.size == size ? rand_set : rand_sum(size, sum)
This is good, however the outputs are not unique. Here's what I've got for example [1, 4, 45, 8, 3, 6, 9, 14, 6, 4] you can see two 6's and two 4's. – Hamid Nazari Jul 11 '14 at 0:49
@HamidNazari You are correct. Although I am making the initial list unique, that doesn't imply when I take the differences that they will be unique, too. Will fix. – O-I Jul 11 '14 at 14:50

So you want n unique non-zero numbers that sum to t. That's equivalent to n unique number (possibly 0) that sum to (t-n). Forgetting about uniqueness for a second, you get that by selecting n from (t-n) + n - 1 = t-1. Then you add one to each.

Algorithm for doing that selection is here:

Now you just have to handle duplicates. Naive way is just run the non-unique algorithm, and if you get duplicates, throw it out and run again, until you don't get duplicates. There's probably a cleaner algorithm.



var randomSum = function(n,t){
  var max = n*(n+1)/2;  
  if(t < max) return 'Input error';
  var list = [], sum = 0, 
  i = n; while(i--){
    var r = Math.random();
    sum += r;
  var factor = t / sum;
  sum = 0;
  i = n; while(--i){
    list[i] = parseInt(factor * list[i]);
    sum += list[i];
  list[0] = t - sum;
  return list;

I'm using a factor to scale the random numbers (@cheeken idea) but I'm adjusting one number at the and to prevent rounding issues. Not the prettiest solution but it does work.



Not the answer you're looking for? Browse other questions tagged or ask your own question.