Avatar of Miguel Oz
Miguel Oz
Flag 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.
C#Visual Basic.NET

Avatar of undefined
Last Comment
Miguel Oz

8/22/2022 - Mon
SOLUTION
Luis Pérez

THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
GET A PERSONALIZED SOLUTION
Ask your own question & get feedback from real experts
Find out why thousands trust the EE community with their toughest problems.
ASKER CERTIFIED SOLUTION
gt2847c

THIS SOLUTION ONLY AVAILABLE TO MEMBERS.
View this solution by signing up for a free trial.
Members can start a 7-Day free trial and enjoy unlimited access to the platform.
See Pricing Options
Start Free Trial
GET A PERSONALIZED SOLUTION
Ask your own question & get feedback from real experts
Find out why thousands trust the EE community with their toughest problems.
Paul_Harris_Fusion

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);
                 }
                   
             }
                 
         }

 
    }

Miguel Oz

ASKER
Simple and easy to read.
Thanks
This is the best money I have ever spent. I cannot not tell you how many times these folks have saved my bacon. I learn so much from the contributors.
rwheeler23