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

migration rejected from stackoverflow.com Jul 11 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 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.

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
3  
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

8 Answers 8

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

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
    
No golf tag on this one. –  Steven Rumbalski Oct 4 '12 at 14:58

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

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

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]]; RandomSample[x]]

Usage

g[500, 10]

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

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

Ruby

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)
end
share
1  
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 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 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: 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

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

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