You are here:

C#/How to generate combinations faster

Advertisement


Question
QUESTION: Hello Murat,
I created a program about to generate combinations without repetitions

using the for() loop, but i realize that using these for() loops, when

the set of numbers is large, it take lots of time to generate the

combinations, could you tell me, if there is another way to do this

faster and give me an example, thanks.

ANSWER: Hi there,

You should use multi threading to achieve this task. You have to post me your code to go over it and show you an alternative way. However to explain it in simple manner, instead of first For loop, you have to start threads with Task class, add them to an array, wait them to finish with Task.WaitAll(tasks), then combine these arrays to build a new full array or you can simply print results by printing arrays by turns.

Hope that helps,

Murat

---------- FOLLOW-UP ----------

QUESTION: Hello Murat,
This is what it does this program:

1) Print string[] firstArray.
2) Print string[] secondArray.
3) Print the rows that both arrays have equal

but takes about 8 minutes to do all this.
Thanks for help me.

private void button1_Click(object sender, EventArgs e)
       {
         string[] firstArray = { "3", "5", "8", "14", "17", "18", "20", "21", "23", "25", "26", "27",
         "29", "32", "34", "36", "37", "39" };
         string[] secondArray = { "3", "5", "8", "9", "11", "12", "13", "14", "15", "17", "18", "21",
         "25", "26", "27", "32", "34", "36", "38", "39", "38" };
         string primerArray = "";
         string segundoArray = "";

         int combinationCounterFirstArray = 0;
         int combinationCounterSecondArray = 0;
         int rowUniqueCounter = 0;
         int columns = 5;

         // Print string[] firstArray.
         for (int i = 0; i < firstArray.Length - 4; i++)
         {
         for (int j = i + 1; j < firstArray.Length - 3; j++)
         {
         for (int k = j + 1; k < firstArray.Length - 2; k++)
         {
         for (int l = k + 1; l < firstArray.Length - 1; l++)
         {
         for (int o = l + 1; o < firstArray.Length; o++)
         {
         dataGridView1.Rows.Add();
         ++combinationCounterFirstArray;

         dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[0].Value = combinationCounterFirstArray;
         dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[1].Value = firstArray[i];
         dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[2].Value = firstArray[j];
         dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[3].Value = firstArray[k];
         dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[4].Value = firstArray[l];
         dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[5].Value = firstArray[o];

         primerArray = primerArray + firstArray[i] + " " + firstArray[j] + " " + firstArray[k] + " " +
         firstArray[l] + " " + firstArray[o] + " ";
         }
         }
         }
         }
         }          

         // Print string[] secondArray.
         for (int i = 0; i < secondArray.Length - 4; i++)
         {
         for (int j = i + 1; j < secondArray.Length - 3; j++)
         {
         for (int k = j + 1; k < secondArray.Length - 2; k++)
         {
         for (int l = k + 1; l < secondArray.Length - 1; l++)
         {
         for (int o = l + 1; o < secondArray.Length; o++)
         {
         dataGridView2.Rows.Add();
         ++combinationCounterSecondArray;

         dataGridView2.Rows[combinationCounterSecondArray - 1].Cells[0].Value = combinationCounterSecondArray;
         dataGridView2.Rows[combinationCounterSecondArray - 1].Cells[1].Value = secondArray[i];
         dataGridView2.Rows[combinationCounterSecondArray - 1].Cells[2].Value = secondArray[j];
         dataGridView2.Rows[combinationCounterSecondArray - 1].Cells[3].Value = secondArray[k];
         dataGridView2.Rows[combinationCounterSecondArray - 1].Cells[4].Value = secondArray[l];
         dataGridView2.Rows[combinationCounterSecondArray - 1].Cells[5].Value = secondArray[o];

         segundoArray = segundoArray + secondArray[i] + " " + secondArray[j] + " " + secondArray[k] + " " +
         secondArray[l] + " " + secondArray[o] + " ";
         }
         }
         }
         }
         }
     
         int[,] myFirstArray = new int[combinationCounterFirstArray, 5];

         for (int i = 0; i < combinationCounterFirstArray; i++)
         {
         string[] myStringArray = primerArray.Split(' ');

         for (int j = 0; j < 5; j++)
         {
         myFirstArray[i, j] = Convert.ToInt32(myStringArray[(i * 5) + j]);
         }          
         }

         int[,] mySecondArray = new int[combinationCounterSecondArray, 5];

         for (int i = 0; i < combinationCounterSecondArray; i++)
         {
         string[] myStringArray = segundoArray.Split(' ');

         for (int j = 0; j < 5; j++)
         {
         mySecondArray[i, j] = Convert.ToInt32(myStringArray[(i * 5) + j]);
         }
         }

         // Print the rows that both arrays have equal
         for (int i = 0; i < combinationCounterSecondArray; i++)
         {
         bool rowUnique = true;  
         
         for (int j = 0; j < combinationCounterFirstArray; j++)
         {
         if (compareTwoDimensionalArrays(ref mySecondArray, i, ref myFirstArray, j, ref columns) == true)
         {
         rowUnique = false;
         break;
         }
         }
         if (!rowUnique)
         {
         dataGridView3.Rows.Add();

         for (int k = 0; k < 5; k++)
         {
         dataGridView3.Rows[rowUniqueCounter].Cells[0].Value = rowUniqueCounter + 1;
         dataGridView3.Rows[rowUniqueCounter].Cells[k + 1].Value = mySecondArray[i, k];
         }
         rowUniqueCounter++;
         }
         }
       }

static bool compareTwoDimensionalArrays(ref int[,] firstArray, int firstArrayFirstRow, ref int[,] secondArray, int secondArrayFirstRow, ref int numelements)
       {
         for (int i = 0; i < numelements; i++)
         {
         if (firstArray[firstArrayFirstRow, i] != secondArray[secondArrayFirstRow, i])
         return false;
         }
         return true;
       }

ANSWER: Why have you built 4 "for loop"s twice? That's a great performance loss.
I'm not a mathematician but in this link they achieve this with 3 "for loop"s.

Try to fix your code according to that algorithm.

---------- FOLLOW-UP ----------

QUESTION: Hello Murat,
I am sorry for the code i send you, it is too blend. I checked the link that you send me and he use 3 "for loop"s because he want to print 3 columns, in other words he want to fill a 2d array[120,3]. In my case i want to print 5 columns, for this reason i use 5 "for loop"s.
I built 5 "for loop"s twice because i want to print 2 arrays with different length.

// Print string[] firstArray.
for (int i = 0; i < firstArray.Length - 4; i++)
{
   for (int j = i + 1; j < firstArray.Length - 3; j++)
   {
       for (int k = j + 1; k < firstArray.Length - 2; k++)
       {
         for (int l = k + 1; l < firstArray.Length - 1; l++)
         {
         for (int o = l + 1; o < firstArray.Length; o++)
         {
         dataGridView1.Rows.Add();
         ++combinationCounterFirstArray;

     dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[0].Value = combinationCounterFirstArray;
     dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[1].Value = firstArray[i];
     dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[2].Value = firstArray[j];
     dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[3].Value = firstArray[k];
     dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[4].Value = firstArray[l];
     dataGridView1.Rows[combinationCounterFirstArray - 1].Cells[5].Value = firstArray[o];

     primerArray = primerArray + firstArray[i] + " " + firstArray[j] + " " + firstArray[k] + " " +
         firstArray[l] + " " + firstArray[o] + " ";
         }
         }
       }
   }
}

Can you run my code and show me the way i can get a better performance, once again thanks.

Answer
I have tried to implement what was in my mind and it worked faster.
- First of all, datagridview usage is last thing you should do on tasks like this.
- I showed it in console, but you can write to a single string and in the end, write string to a file. I strongly advise to use StringBuilder if you will do that. So here is the code.
Don't forget to add "using System.Threading.Tasks;".

           for (int i = 0; i < firstArray.Length - 4; i++)
           {
               List<Task> tasks = new List<Task>();
               tasks.Add(Task.Factory.StartNew(() =>
               {
                   for (int j = i + 1; j < firstArray.Length - 3; j++)
                   {
                       for (int k = j + 1; k < firstArray.Length - 2; k++)
                       {
                           for (int l = k + 1; l < firstArray.Length - 1; l++)
                           {
                               for (int o = l + 1; o < firstArray.Length; o++)
                               {
                                   string row = "";
                                   ++combinationCounterFirstArray;


                                   row = combinationCounterFirstArray.ToString();
                                   row += " " + firstArray[i];
                                   row += " " + firstArray[j];
                                   row += " " + firstArray[k];
                                   row += " " + firstArray[l];
                                   row += " " + firstArray[o];
                                   Console.WriteLine(row);
                               }
                           }
                       }
                   }
               }));
               Task.WaitAll(tasks.ToArray());
               
           }


In my case it was completed under a minute, however as normal, rows are not in sequential order since they are calculated in a parallel space.

Hope that helps,

Murat

C#

All Answers


Answers by Expert:


Ask Experts

Volunteer


Murat Mehmet

Expertise

I can help with questions about desktop and web programming in C#, including SOAP, XML, database managing, custom controls, security etc.

Experience

I have been developing web and especially desktop applications in C# and VB.Net for almost 5 years. My programming life has begun with VB6 long time ago, so its about 8 years that I am in this business.

Organizations
Was in R & D for 2 years in a popular Turkish technology website: cyber-warrior.com

Education/Credentials
2011 Computer Engineering graduation in University of Trakia in Turkey.

©2016 About.com. All rights reserved.