2
\$\begingroup\$

I have written an algorithm in C#. It is recursive, but it is not optimal. Maybe you have suggestions for improvement? (I already posted this question on stackoverflow but the question was closed there).

This is the exercise (I made it up myself). There are 3 or more buckets and there are 4 or more balls. The goal is to calculate every combination to distribute all balls over all buckets. There must be at least 1 ball in a bucket.

For example: if you have 3 buckets and 5 balls you get these combinations (as produced by the program):

Balls:3 1 1 | Total = 5
Balls:2 2 1 | Total = 5
Balls:1 3 1 | Total = 5
Balls:1 2 2 | Total = 5 <-- This one is unwanted
Balls:2 1 2 | Total = 5
Balls:1 2 2 | Total = 5
Balls:1 1 3 | Total = 5

Explanation: There is a separate class Balls, which is a list of integers. Depth and branchingfactor determine the number of buckets and the number of balls. The first combination starts with the maximum number of balls in the first bucket and 1 in the other buckets. Then 1 ball is taken out of the first bucket and is put in the second bucket and so on.

This is the code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace BallBruteForce
{
    class Program
    {
        //Final result is stored in List
        static List<Balls> BallsList=new List<Balls>();
        static int Depth = 5;
        static int BranchingFactor = 10;

        static int minComp;
        static int maxComp;

        static void Main(string[] args)
        {
            minComp = 1;
            maxComp= BranchingFactor - (Depth-1)*minComp;

            Stopwatch sw = new Stopwatch();
            sw.Start();
            startBruteForce(Depth);
            sw.Stop();

            Console.WriteLine("Time elapsed: " + sw.Elapsed);
            Console.WriteLine("Press Enter to Exit");
            Console.ReadLine();
        }

        private static void startBruteForce(int keyLength)
        {
            var ratioArray = createArray(keyLength);

            BallsList.Add(ratioArray);

            int count = 1;
            Console.WriteLine(count +". " + ratioArray);

            createNewArray(0, keyLength, ratioArray, ref count);
            Console.WriteLine("Total processed: " + count);
        }

        private static void createNewArray(int curCol, int length, Balls ratioArray, ref int count)
        {
            Balls copyArray = new Balls(ratioArray);

            if (ratioArray[0] > minComp)
            {

                if (curCol == 0)
                {
                    Balls baseArray = new Balls(ratioArray);
                    for (int i = 1; i < length; i++)
                    {
                        createNewArray(i, length, copyArray, ref count);
                    }
                }
                else
                {
                    copyArray[0]--;
                    copyArray[curCol]++;

                    BallsList.Add(copyArray);
                    count++;
                    Console.WriteLine(count + ". " + copyArray);
                    createNewArray(0, length, copyArray, ref count);
                }
            }
        }

        private static Balls createArray(int length)
        {
            Balls ballsC = new Balls();
            ballsC.Add(maxComp);
            for (int i = 1; i < length; i++)
            {
                ballsC.Add(minComp);
            }

            return ballsC;
        }

        class Balls : List<int>
        {
            public Balls() { }

            public Balls(Balls newSds)
            {
                newSds.ForEach((item) =>
                {
                    this.Add(item);
                });
            }

            public override string ToString()
            {
                StringBuilder sb = new StringBuilder();
                sb.Append("Balls:");
                foreach (int sd in this)
                {
                    sb.AppendFormat("{0} ", sd);
                }
                sb.AppendFormat("| Total = {0} ", this.Sum());
                return sb.ToString();
            }
        }

    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Why is that one unwanted? \$\endgroup\$ – ANeves wants peace for Monica Jun 28 '12 at 9:05
  • 1
    \$\begingroup\$ Looks like it's because a different permutation of putting balls in buckets produces the same combination of balls in buckets. See the combination two rows down; same thing, probably produced with a different sequence. \$\endgroup\$ – KeithS Jul 19 '12 at 17:28
2
\$\begingroup\$

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

  1. To make this run faster, use memoization for the function getCombinationsRecursive().

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

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

  4. Write the results right to left by appending instead of putting the new values in front of the subResults.

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

\$\endgroup\$
1
\$\begingroup\$

The obvious answer (for the unwanted duplicate) is to maintain a set of the previous column counts. So when it comes to (the second) [1,2,2], you can check whether it's in the set of { [3,1,1], [2,2,1], [1,3,1], [1,2,2], [2,1,2] } and conclude that you don't want to print the line and so exit the recursion.

This won't block the specific one you want, but I don't think it should matter wrt the results.

\$\endgroup\$
0
\$\begingroup\$

This is a base 3 number, of 5 digits (with the extra note that each digit must have +1 to it and total for all digits must equal 5). I based this on my own SO answer here: https://stackoverflow.com/a/9315076/360211

class Program
    {
        static void Main()
        {
            int balls = 5;
            int buckets = 3;
            int maxInBucket = balls - buckets + 1; //because of rule about must be 1
            int baseN = maxInBucket;
            int maxDigits = buckets;
            var max = Math.Pow(baseN, maxDigits);
            for (int i = 0; i < max; i++)
            { // each iteration of this loop is another unique permutation 
                var digits = new int[maxDigits];
                int value = i;
                int place = digits.Length - 1;
                while (value > 0)
                {
                    int thisdigit = value % baseN;
                    value /= baseN;
                    digits[place--] = thisdigit;
                }
                var totalBallsInThisCombo = digits.Sum(d => d + 1); //+1 because each bucket always has one in it
                if (totalBallsInThisCombo != balls)   //this is the implementation of rule about must = 5
                {
                    continue;
                }
                Console.Write("Balls: ");
                foreach (var digit in digits)
                {
                    Console.Write(digit + 1); //+1 because each bucket always has one in it
                    Console.Write(" ");
                }
                Console.WriteLine("| Total = {0}", totalBallsInThisCombo);
            }
            Console.ReadLine();
        }
    }
\$\endgroup\$
0
\$\begingroup\$

I would approach the algorithm in the following way:

  • All cases start with either one, two or three balls being places in the first bucket. So, do each of these.
  • For each of the above cases, recurse through putting balls in the second bucket, following your rules (meaning that you cannot put so many balls in the second bucket that you cannot put at least one ball in the third bucket).
  • For each of THOSE cases, put all remaining balls in the third bucket.

Doing it this way, there's only one algorithmic path to follow that will result in the balls being in the buckets in a particular combination; 1-3-1 is arrived at by putting one ball in the first, then three balls in the second, then one ball in the last; not by starting with 3-1-1 and then moving balls to produce the progressions 2-2-1 -> 2-1-2 -> 1-2-2 OR 2-2-1 -> 1-3-1 -> 1-2-2, as your algorithm is currently doing.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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