Link to home
Start Free TrialLog in
Avatar of Miguel Oz
Miguel OzFlag for Australia

asked on

Help optimizing code for combination of Numbers

I would like your expert advice on how to optimize the following code:
        private void PrintCombinations(int total)
        {
            for (int i = 0; i <= total; i++)
            {
                for (int j = 0; j <= total; j++)
                {
                    for (int k = 0; k <= total; k++)
                    {
                        if ((i + j + k) == total)
                           Debug.WriteLine(String.Format("{0},{1},{2}", i, j, k));break;
                   }
                }
            }
        }

Open in new window


For example, if we call the method as PrintCombinations(6), the results should be like:
0,0,6
0,1,5
0,2,4
...
6,0,0

The code above is non optimized. For example, code do not need to loop k form 0 to 6 to get 0,1,5 and 0,2,4.
SOLUTION
Avatar of Luis Pérez
Luis Pérez
Flag of Spain image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
It depends what you mean by optimise!

The posts already made demonstrate how to make the code more succint.

I thought it would be interesting to generalise it.

Here is a class that will do the job for user-defined totals and sequence length.


To use it, do something like:
            Proposed p = new Proposed();

            p.OutputCombinations (3,6);   //  3 numbers that total 6

            p.OutputCombinations (4,5);   // 4 numbers that total 5
            p.OutputCombinations (3,10);  // you get the idea ....



    class Proposed
    {

        private int _targetTotal;
        private int _numItems;
        private int[] _row;

        public void OutputCombinations(int numItems, int targetTotal)
        {
            _targetTotal = targetTotal;
            _numItems = numItems;
            _row = new int[numItems];

            _outputCombinations(0, 0);
        }

       
         private void _outputCombinations(int currentIndex, int currentTotal)
         {
             if (currentIndex == _numItems - 1)
             {
                 /* We are at the last positionso set the only legal remaining value */
                 _row[currentIndex] = _targetTotal - currentTotal;

                 /* Output the line */
                 StringBuilder sb = new StringBuilder();
                 for (int i = 0; (i < _numItems); i++)
                 {
                     if (sb.Length > 0) sb.Append(',');
                     sb.Append(_row.ToString());
                 }

                 System.Diagnostics.Debug.WriteLine(sb.ToString());

             }
             else
             {
                 /* Recursive call to this routine to fill the rest of the row */
                 for (int currentValue =0 ; currentValue < _targetTotal - currentTotal; currentValue++)
                 {
                     _row[currentIndex] = currentValue;
                     _outputCombinations(currentIndex + 1, currentTotal + currentValue);
                 }
                   
             }
                 
         }

 
    }

Avatar of Miguel Oz

ASKER

Simple and easy to read.
Thanks