There's a better way
If there are 5 balls and 3 buckets, but each bucket must contain at least 1 ball, imagine the following set of balls:
O O O O O
Rather than moving the balls around, we can move buckets.
That is, I will mark 3 balls with an 'x' and that ball and the balls to the left of it (until the next 'x') are part of the bucket, (since all balls are in a bucket, the right-most ball must be marked.
So we get:
x x O O x , x O x O x , x O O x x , O x x O x , O x O x x , O O x x x
Code to solve 3 buckets, N balls
private static readonly int NumOfBuckets = 3;
private static readonly int NumOfBalls = 8;
private static string getCombinations()
{
int numBuckets = 3;
int numBalls = 5;
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= numBalls - 2; i++)
{
int ballsInBucket1 = i;
for (int j = i + 1; j <= numBalls - 1; j++)
{
int ballsInBucket2 = (j - 1);
int k = numBalls;
int ballsInBucket3 = k - j;
string s = "Balls:" + ballsInBucket1 + " " + ballsInBucket2 + " " + ballsInBucket3 + " | Total = 5";
sb.AppendLine(s);
}
}
return sb.ToString();
}
static void Main(string[] args)
{
string result = getCombinations();
Console.WriteLine(result);
Console.ReadLine();
}
Basically the code is using i,j, and k to mark x's on the balls, and then we get the number of balls out. We don't need to remove any duplicates, since we generated just Combinations, and not permutations.
This code works for 3 buckets and n balls.
But because of the 2 hard-coded For loops this won't work for more or less buckets.
Using Recursion to Infinitely Nest the For Loops
The real difficulty here is that each possible combination needs to be written as a line on the console. This means that our recursive function needs to be able to return multiple lines, and add to each line as the recursion comes back.
The Base case of the recursion is easy, if there is just 1 bucket, put all the rest of the balls in it.
Otherwise we loop through the number of balls we can put in the first bucket, and recurse with a smaller problem size, then add the first number of balls to each of those results coming back.
We use a recursive function which is called by a helper function so that we can move the timing code into a separate place.
Code to solve M buckets, N balls
private static string getCombinationsRecursiveHelper()
{
StringBuilder sb = new StringBuilder();
string[] subResult = getCombinationsRecursive(NumOfBuckets, NumOfBalls);
for( int i = 0; i < subResult.Length; i++)
{
sb.AppendLine( "Balls:" + subResult[i] + " | Total = " + NumOfBalls );
}
return sb.ToString();
}
private static string[] getCombinationsRecursive( int numBuckets, int numBalls)
{
if (numBuckets == 1)
{
return new string[]{numBalls.ToString()};
}
int numBuckets_minus_1 = numBuckets - 1;
int bound = numBalls - numBuckets_minus_1;
long numOfPossibilities = NChooseK( numBalls - 1, numBuckets_minus_1);
string[] result = new string[ numOfPossibilities ];
int current = 0;
for (int i = 0; i < bound; i++)
{
string[] subResult = getCombinationsRecursive(numBuckets - 1, numBalls - (i+1));
for (int j = 0; j < subResult.Length; j++)
{
result[current] = (i+1).ToString() + " " + subResult[j];
current++;
}
}
return result;
}
private static long NChooseK(long n, long k)
{
long result = 1;
for (long i = Math.Max(k, n - k) + 1; i <= n; ++i)
result *= i;
for (long i = 2; i <= Math.Min(k, n - k); ++i)
result /= i;
return result;
}
static void Main(string[] args)
{
Console.WriteLine("Starting Program");
Console.WriteLine("");
string result = getCombinationsRecursiveHelper();
Console.BufferHeight = result.Length;
Console.WriteLine( result );
Console.WriteLine("");
Console.WriteLine("Press Enter to Exit");
Console.ReadLine();
*/
}
I make use of an NChooseK function so we can determine how large the string[] needs to be to hold the results from the subproblems which will be carried out at the next level down in recursion.
Full Code with Timing Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace BallsInBins
{
class Program
{
private static readonly int NumOfBuckets = 8;
private static readonly int NumOfBalls = 12;
private static double AverageMilliseconds = -1.0;
static void Main(string[] args)
{
Console.WriteLine("Starting Program");
Console.WriteLine("");
string result = DoTiming( getCombinationsRecursiveHelper );
Console.BufferHeight = result.Length;
Console.WriteLine( result );
Console.WriteLine("");
Console.WriteLine("ElapsedTime: {0:N8} Milliseconds.", AverageMilliseconds);
Console.WriteLine("");
Console.WriteLine("Press Enter to Exit");
Console.ReadLine();
}
private static readonly int MinTimingVal = 1000;
private static readonly int MinLoopTimingVal = 1000;
/// <summary>
/// Times how long in Milliseconds a function takes which returns a string.
/// Complies with best timing practices.
/// Does not make timings of less than 1 full second, warms up the code
/// for the JIT compiler before timing, gets average time spent per iteration,
/// and accounts for the looping overhead in a similar manner.
/// </summary>
/// <param name="a"> Func<string> theActionToTime</param>
/// <returns>The string result of the function.</returns>
private static string DoTiming(Func<string> a)
{
string result = a.Invoke();
Stopwatch watch = new Stopwatch();
Stopwatch loopWatch = new Stopwatch();
bool shouldRetry = false;
int numOfIterations = 1;
do
{
watch.Start();
for (int i = 0; i < numOfIterations; i++)
{
a.Invoke();
}
watch.Stop();
shouldRetry = false;
if (watch.ElapsedMilliseconds < MinTimingVal) //if the time was less than the minimum, increase load and re-time.
{
shouldRetry = true;
numOfIterations *= 2;
watch.Reset();
}
} while (shouldRetry);
long totalTime = watch.ElapsedMilliseconds;
double avgloopingTime = getLoopingTime(numOfIterations);
double avgMilliseconds = (((double)totalTime) / (double)numOfIterations) - avgloopingTime;
TimeSpan t = TimeSpan.FromMilliseconds(avgMilliseconds);
AverageMilliseconds = avgMilliseconds;
Debug.WriteLine("ElapsedTime: {0:N8} Milliseconds.", avgMilliseconds);
return result;
}
private static double getLoopingTime(int numOfIterations)
{
int wrmUpTimes = 3;
int outerLoop = 2;
long elapsedTime = -1L;
double avg = 0.0;
Stopwatch watch = new Stopwatch();
for (int wrm = 0; wrm < wrmUpTimes; wrm++)
{
watch.Start();
for (int i = 0; i < outerLoop; i++)
{
for (int j = 0; j < numOfIterations; j++)
{
; //time how long an empty loop takes.
}
}
watch.Stop();
elapsedTime = watch.ElapsedMilliseconds;
if (elapsedTime < MinLoopTimingVal)
{
wrm--;
outerLoop *= 2;
}
else
{
avg = elapsedTime / (double)outerLoop;
}
}
return avg;
}
private static string getCombinationsRecursiveHelper()
{
StringBuilder sb = new StringBuilder();
string[] subResult = getCombinationsRecursive(NumOfBuckets, NumOfBalls);
for( int i = 0; i < subResult.Length; i++)
{
sb.AppendLine( "Balls:" + subResult[i] + " | Total = " + NumOfBalls );
}
return sb.ToString();
}
private static string[] getCombinationsRecursive( int numBuckets, int numBalls)
{
if (numBuckets == 1)
{
return new string[]{numBalls.ToString()};
}
int numBuckets_minus_1 = numBuckets - 1;
int bound = numBalls - numBuckets_minus_1;
long sumOfPossibilities = NChooseK( numBalls - 1, numBuckets_minus_1);
string[] result = new string[ sumOfPossibilities ];
int current = 0;
for (int i = 0; i < bound; i++)
{
string[] subResult = getCombinationsRecursive(numBuckets - 1, numBalls - (i+1));
for (int j = 0; j < subResult.Length; j++)
{
result[current] = (i+1).ToString() + " " + subResult[j];
current++;
}
}
return result;
}
private static long NChooseK(long n, long k)
{
long result = 1;
for (long i = Math.Max(k, n - k) + 1; i <= n; ++i)
result *= i;
for (long i = 2; i <= Math.Min(k, n - k); ++i)
result /= i;
return result;
}
}
}
This includes timing code which runs the algorithm enough times to take longer than a full second, then divides by the number of iterations so you can get an average time elapsed (also it subtracts the average amount of time it took to loop that many times).
On my computer this computes 16 buckets and 24 balls in an average 2,278 milliseconds.
(Of course, printing the solution to the console takes a lot longer)
Other Optimizations/Changes
To make this run faster, use memoization for the function getCombinationsRecursive().
Use BigInteger in the NChooseK instead of longs to support larger numbers, but then you will also need to use something other than string[] for the results for very large instances.
Use parallelism if you don't care about the order in which the results get written (although as it stands, that could be difficult with this implementation).
Write the results right to left by appending instead of putting the new values in front of the subResults.
Completely change the algorithm to do a depth-first search over the possibilities instead of a breadth first search, that way each result could be written one at a time, instead of needing to store it all back out of the recursion.
