creating a method to return a range of random values

Question

Consider the following code. The basic idea is to return a comma separated list of 20 numbers any of which can be a value between 0 and the max allowed value. On each pass through the loop the potential max value allowed for the next value in the list reduces by whatever last random value picked was.

So it works... but it sucks. The problem being it's always going to produce output like this:

"22,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0"

"17,3,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0"

"23,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0"

How could it be modified to allow for a more even distribution of values across the range?

    public static string RandomRangeOfValuesMaker(int total)
    {
        var remainingTotal = total + 1;

        const int numberOfValues = 20;

        var rand = new Random();

        var builder = new StringBuilder();

        for (var i = 1; i < numberOfValues + 1; i++)
        {
            var currentRandomNumber = rand.Next(remainingTotal);

            remainingTotal = remainingTotal - currentRandomNumber;

            builder.Append(currentRandomNumber + ",");
        }

        var rangeOfValues = builder.ToString().Remove(builder.ToString().Length - 1);

        return rangeOfValues;
    }

Answer 1

UPDATE: I misunderstood the poorly stated constraints on the problem; my original answer addresses the problem "Generate n random numbers less than m, in descending order". Original answer is appended below.

The actual problem is "generate a random partition of the number m into n parts".

There are many ways to do that. Here's one; it is O(m) in time and O(n) in space. Can you improve that?

static Random random = new Random();
static IEnumerable<int> Partition(int number, int parts) {
  int[] partition = new int[parts];
  for(int i = 0; i < number; ++i)
    partition[random.Next(parts)] += 1;
  return partition;
}

The algorithm is: we have parts crates and number apples; we randomly throw each apple into a crate until we're out of apples, and we have partitioned all the apples.

Now your program is the one-liner

Partition(maxNumber, 20).OrderByDescending(x=>x).CommaSeparated();

using the helper functions below.

The key thing to note in both this solution and Kyle's solution is not the algorithm that generates the partition -- like I said, there are lots of ways to do that. Rather, the key thing is don't try to do too much in one function. You went wrong when you tried to ensure the sum property and the monotonicity and the comma separation all in the same place. Sorting 20 numbers is cheap; outsource the problem. Comma-separating a bunch of stuff is cheap; outsource that problem too. Write small functions that each do one thing well, and then compose them into larger functions.

---

How could it be modified to allow for a more even distribution of values across the range?

Choose the numbers first and then sort them.

Let's break it down. First: an infinite sequence of random numbers:

private static Random random = new Random();    
public static IEnumerable<int> RandomNumbers(int max)
{
  while(true) yield return random.Next(max);
}

Now that you have that your program becomes a one-liner.

public static string RandomRangeOfValuesMaker(int maxNumber)
{
  return string.Join(",", RandomNumbers(maxNumber).Take(20).OrderByDescending(x=>x));
}

Any time you are doing something involving a sequence, as yourself can I use built-in sequence operators to express my desired workflow? Can I build my own sequence operators?

For example, we could make another sequence operator one-liner:

public static string CommaSeparated<T>(this IEnumerable<T> items) 
{
  return string.Join(",", items);
}

And now your program becomes even more elegant:

public static string RandomRangeOfValuesMaker(int maxNumber)
{
  return RandomNumbers(maxNumber)
    .Take(20)
    .OrderByDescending(x=>x)
    .CommaSeparated();
}

What do you want? 20 random numbers, ordered in descending order, separated by commas. So how should your program read? It should say I want 20 random numbers ordered descending, separated by commas. Write your program so that it looks like a description of the problem it is trying to solve. It will be easier to understand, easier to maintain, and easier to see that it is correct.

Answer 2

If you want a sequence of random integers that add up to a particular sum, the easiest thing is to first pick a sequence of random integers in the range [0, sum], sort them, then return the differences:

public static IEnumerable<int> GetSequenceWithSum( Random rand, int count, int sum )
{
    // Get a list of count-1 random numbers in the range [0, sum] in ascending order.
    // This partitions the range [0, sum] into count different bins of random size.
    var partition = Enumerable.Range( 0, count - 1 )
                              .Select( _ => rand.Next( 0, sum + 1 ) )
                              .OrderBy( x => x );

    // Yield the size of each partition in the range.
    int previous = 0;
    foreach( int value in partition )
    {
        yield return value - previous;
        previous = value;
    }

    yield return sum - previous;
}

I can't say precisely what distribution this gives you, but it will give you one that looks "even".

The simplest way to understand why this works is to think of it this way:

Say you want a bunch of sticks of random length, but when you glue the sticks together you want their lengths to add up to some specific length.

One way to accomplish this is to start with a stick of the length you want and to cut it randomly into the number of pieces you want. That way the sum of the lengths of each of the pieces is the length of the piece you started with.

This code "cuts" the stick by first picking random numbers which represent the locations at which we'll cut the big stick. It then puts the cut positions in order so we know which cuts are next to each other. Then all it has to do is subtract consecutive cuts to get the lengths of the stick pieces.

Answer 3

I'll preface this with: Read the answer from Eric Lippert - what he says is almost certainly more correct than me (pssst.. he studied Mathematics at University AND worked on the C# compiler, amongst other things, at Microsoft!).

A rudimentary implementation of your requirement that the function return X values that sum to Y could be written as:

public static string StringyRandomNumbersThatAddUpToMaxNumber(int sumOfRandomNumbers, int numberOfValuesToReturn)
{
    var randomNumbers = RandomNumbersThatAddUpToMaxNumber(new List<int>(), sumOfRandomNumbers, numberOfValuesToReturn);
    return string.Join(",", randomNumbers);
}

public static IEnumerable<int> RandomNumbersThatAddUpToMaxNumber(List<int> randomNumbers, int sumOfRandomNumbers, int numberOfValuesToReturn)
{
    var randomNumberGenerator = new Random();

    while (randomNumbers.Sum() < sumOfRandomNumbers)
    {
        var ceiling = (randomNumbers.Any() ? randomNumbers.Sum() : sumOfRandomNumbers) / 2;
        var newNumber = randomNumberGenerator.Next(ceiling);

        if (randomNumbers.Sum() + newNumber <= sumOfRandomNumbers)
        {
            randomNumbers.Add(newNumber);
        }
    }

    if (numberOfValuesToReturn > randomNumbers.Count())
    {
        randomNumbers.Remove(randomNumbers.Max());

        return RandomNumbersThatAddUpToMaxNumber(randomNumbers, sumOfRandomNumbers, numberOfValuesToReturn);
    }

    return randomNumbers;
}

In theory, it may never return or throw a StackOverflowException, but in practice it's likely that it will.

I'm not in any way, shape, or form confident that the resultant numbers could be considered to be truly random (as it eliminates the highest value on each recursion to allow it more "working space" to find more values to satisfy the requirement that they all add up to Y), so please take this code with that note.