Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
3  
What random distribution? Even distribution over the naturals isn't possible. –  Aaron Dufour Oct 3 '12 at 2:21
5  
What's the winning criterion? –  grc Oct 3 '12 at 3:19
1  
+1 Nice question and interesting to solve. –  David Carraher Oct 3 '12 at 13:22
3  
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
1  
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
show 5 more comments

migrated from stackoverflow.com Oct 3 '12 at 2:08

This question came from our site for professional and enthusiast programmers.

8 Answers

Mathematica

Edit

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

Code

g[n_, partitions_] := Module[{f, x},
   f[n1_, p1_] := Sort[Length /@ (IntegerDigits /@ 
   Flatten@ImportString[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]]; x]

Usage

g[500, 10]

{11, 19, 20, 27, 38, 48, 59, 65, 89, 124}

Total[%]

500

Analysis

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.

share|improve this answer
    
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. –  David Carraher Oct 3 '12 at 13:26
add comment

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]

Explanation:

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.

share|improve this answer
    
No golf tag on this one. –  Steven Rumbalski Oct 4 '12 at 14:58
add comment

Python

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]
        return
    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...

share|improve this answer
    
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 http://dl.acm.org/citation.cfm?id=1024669, 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 algo.inria.fr is currently unresponsive and I can't check. –  boothby Oct 5 '12 at 5:40
add comment

Python

Input is given as [n, t]

Note that these solutions are extremely slow ;)

Ungolfed:

import random
b=input()
a=[]
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
b=input()
a=c=range(1,b[1])
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.

share|improve this answer
    
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
add comment

Python

Takes input from the variables n and t

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

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.

share|improve this answer
add comment

Generate the n numbers as you would normally, take their sum s, and then scale each one's value by a factor of t/s (or n(n+1)/(2s)), rounding as appropriate.

share|improve this answer
    
rounding is a bit tricky... –  Karoly Horvath Oct 3 '12 at 1:25
    
Also, this won't actually give a uniform distribution on the set of possible outputs. (Try it out with, say, n = 2 if you don't believe me.) –  Ilmari Karonen Oct 3 '12 at 9:13
    
Ilmari is right: ideone.com/6OEqa Also, as others have noted, OP needs to specify "randomly distributed". If it means uniform distribution of the N numbers, then no. If it means "of the possible sets of N numbers that sum to S, each set is equally likely", then yes. –  GigaWatt Oct 3 '12 at 21:12
add comment

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: http://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values

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.

share|improve this answer
add comment

Javascript

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();
    list.push(r);
    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.

Demo

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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