Combinations in C++, Part 2

, 8 Apr 2009 CPOL
 Rate this:
Introduce 4 new algorithms on finding combinations

Introduction

There are 4 new algorithms present in this article. The first one is about speed optimization by using integers as array indexes (I'll explain that later). The second one is about concurrent programming (now with multi-core CPUs becoming mainstream in the near future, you can cut the time to find a lot of combinations by half and more). The third and fourth ones deal with finding combinations with repetitions.

In my articles, I place a strong emphasis to explain the techniques as clearly as possible. It is of utmost importance for you, the reader, to understand the explanations. Because once you understand them, you need not know how I do it; you can implement it yourself, even in your favourite computer language. You can implement it yourself, or in an iterative way? Recursive way? Your way? Heck! Your implementation could even be faster than mine, who knows?

Source Code Version

For the source code changes, all the classes and functions fall under the `stdcomb` namespace and they are given a name called "Combination Library" and a version (1.5.0), so that the users know which is the latest version, as there are a few copies of source code floating around the Internet. Always get the latest version, as it contains new features and/or bug-fixes. You can always be sure that CodeProject has the most up-to-date version.

Another Way of Finding the Combinations

Combination is the way of picking a different unique smaller sequence from a bigger sequence, without regard to the ordering (positions) of the elements (in the smaller sequence). This article teaches you how to find combinations. For every technique presented in this article, I will explain it as well as I can before going on to teach you how to use the source code.

n : n is the larger sequence from which r sequence is picked

r : r is the smaller sequence picked from n sequence.

c : c is the formula for the total number of possible combinations of r picked from n distinct objects : n! / (r! (n-r)! )

The ! postfix means factorial.

The Technique for Finding Combinations Without Repetitions

I added this section because I realized the explanation in the original article is not easy for the readers to visualise the underlying pattern. Let me explain the new approach now: the shifting technique.

To find combinations, we will use a technique which involves shifting the last combination element from the left to the right.

Find Combinations of 1 from a Sequence of 5

Let us first find combinations of 1 from a sequence of 5 numbers {0,1,2,3,4}. Please note that the red box is the combination element.

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

Total 5 combinations are generated.

```0
1
2
3
4```

Find Combinations of 2 from a Sequence of 5

For the first example, it is pretty easy, isn't it. Let us go on to find combinations of 2 from a sequence of 5 numbers {0,1,2,3,4}. Please note the red boxes are the combination elements.

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

Oops, we can't shift the last element anymore. Now we shift the first element and bring back the last element to its right side. Shown below.

 0 1 2 3 4

For the next 2 combinations, we continue to shift the last element.

 0 1 2 3 4

 0 1 2 3 4

Again, we cannot shift anymore and shift the first element and bring the last element to its side.

 0 1 2 3 4

Shift last element as usual.

 0 1 2 3 4

Shift the first element and bring the last to its side.

 0 1 2 3 4

Oops, we can shift neither the first nor last element anymore. This is the end of all the combinations generated.

Total 10 combinations are generated.

```01
02
03
04
12
13
14
23
24
34```

Find Combinations of 3 from a Sequence of 5

Let us go on to find combinations of 3 from a sequence of 5 numbers {0,1,2,3,4}. Please note the red boxes are the combination elements. But for this, I will not explain. Observe the pattern.

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

 0 1 2 3 4

Total 10 combinations are generated.

```012
013
014
023
024
034
123
124
134
234```

Steps to Find Combinations

Of course, I can go on to demonstrate finding combinations of 4 elements out of 5 and so on. But I don't. I trust that you can extrapolate the technique for finding different combinations from different sequences.

Let us define the steps for the shifting pattern we used to find all combinations.

• Initially, All the element(s) must be on the leftmost of the array.
• Shift the last red box until it cannot shift anymore, shift the next rightmost red box (if there is one) and bring back the last element to the right side of it. This is the new combination.
• Continue to shift the last element to the right.
• It comes to a point where the last 2 elements cannot shift any longer, then shift the 3rd one (from right) and bring the last 2 to its side consecutively.
• Previous point rephrased for all abitrary cases - ('i' here stands for number). It comes to a point where the last i elements cannot shift any longer, then shift the i+1 element (from right) and bring the last i elements to its side consecutively.
• Continue until all the elements cannot shift any longer, all the combinations have been generated.

Optimised Version: Index Combination

Is there any way we can optimise the technique used in `next_combination()` function? The answer is yes but we have to give up the genericness of the `next_combination()`.

Now, the `next_combination()` compares the element, which it is going to shift, with other elements in the n sequence to know its current position in the n sequence. Let us see if we can get rid of this finding operation.

Take a look at this combination (Take 2 out of 5):

```01234
x x```

If the 2 elements in the r sequence are integers which store its index position in n sequence, then the finding is not needed. And with this method, the combination returned is a combination of the indexes in the n sequence, is no longer a combination of objects. The timing of finding combinations from a sequence of any custom objects is the same, O(1), because integer index is used.

The `==` operator is not needed to be defined for this method to work; next_combination needs it to be defined unless you used the predicate version. Other requirements remain the same. Anyway, finding combinations of objects is actually the same as finding combinations of integers. And integer variables should be faster than class objects because of the object overhead. So we should use this!

This technique is implemented in the `CIdxComb` class. Here is an example on how to use the `CIdxComb` class.

```#include <iostream>
#include <string>
#include <vector>
#include "IndexCombination.h"

using namespace std;
using namespace stdcomb;
void foo()
{
CIdxComb cb;
cb.SetSizes(5,3);
// n sequence
vector<string> vsAnimal;
vsAnimal.push_back( "Elephant" );
vsAnimal.push_back( "Deer" );
vsAnimal.push_back( "Cat" );
vsAnimal.push_back( "Bear" );
vsAnimal.push_back( "Ape" );
// r sequence
vector<unsigned int> vi(3);
vi[0] = 0;
vi[1] = 1;
vi[2] = 2;

cout<< vsAnimal[ vi[0] ] << " "
<< vsAnimal[ vi[1] ] << " "
<< vsAnimal[ vi[2] ] << "\n";

int Total = 1;
while ( cb.GetNextComb( vi ) )
{
// Do whatever processing you want
// ...

cout<< vsAnimal[ vi[0] ] << " "
<< vsAnimal[ vi[1] ] << " "
<< vsAnimal[ vi[2] ] << endl;

++Total;
}

cout<< "\nTotal : " << Total << endl;
}```

Benchmark Between next_combination() and CIdxComb

Below is a benchmark result of `next_combination()` and `CIdxComb` for finding all the combinations of r sequence of 6 from n sequence of 45, 10 times, using `QueryPerformanceCounter()`, on a Intel P4 2.66Ghz CPU and 1GB of DDR2 RAM PC.

`next_combination` - 1925.76 milliseconds
`CIdxComb` - 149.608 milliseconds

This benchmark program is included in the source!

There is a very strange occurrance that `CIdxComb` runs as slow or slower than `next_combination` in some benchmarks in debug build. I don't know why. But I think this difference is due to how iterators (which `next_combination()` used) and array subscript index (which `CIdxComb` used) are handled in `std::vector`. The above result is from a release build without any optimization.

A Helper Algorithm for Concurrency

Let us consider a case that you need to generate lots of combinations, say 100 billion. You have a dual-core CPU PC, so naturally you would want to maximize the dual core by having some concurrent processing (mult-threading). You can do that, if you can tell the 1st thread to calculate combinations starting from the 1st combination and the 2nd thread start from 50 billionth combination number. Each thread will find 50 billion combinations.

The problem is you do not know what combination is at 50 billionth! Let's say you do not have a dual-core CPU PC or SMP PC, you have 4 computers, so how about this: you could tell the 1st computer to calculate from the 1st 25th billion, the 2nd computer the 2nd 25th billion and so on. The missing link here is a way to calculate a combination based on a position in the total number of combinations so that `CIdxComb` or `next_combination()` can continue on finding combination starting from that one.

Fortunately, your hero here, which is me, has figured out a way to do this. The easiest way to explain this method is to walk though a simple example with me.

The Technique of Finding Combination, Given its Index

Let us find out the 92nd combination of 3 out of sequence of 10. Take note in zero-based counting, it would be number 91. In total, there are 120 combinations.

Below are the positions of the combinations which are placed side by side. I am going to show you how I derive the positions later, so right now you take it that they are correct. 1st element is represented by the red box, 2nd the green box and 3rd the blue box.

Let us find the position of the red box first.

0th

 0 1 2 3 4 5 6 7 8 9

36th

 0 1 2 3 4 5 6 7 8 9

64th

 0 1 2 3 4 5 6 7 8 9

85th

 0 1 2 3 4 5 6 7 8 9

100th

 0 1 2 3 4 5 6 7 8 9

110th

 0 1 2 3 4 5 6 7 8 9

116th

 0 1 2 3 4 5 6 7 8 9

119th

 0 1 2 3 4 5 6 7 8 9

Since the one we are going to find is 91st, it falls between 85th and 100th, so the 1st element of the 91st combination is 3.

To find the 2nd element (green box), we must subtract 85 from 91 and the result is 6th combination.

0th

 4 5 6 7 8 9

5th

 4 5 6 7 8 9

9th

 4 5 6 7 8 9

12th

 4 5 6 7 8 9

14th

 4 5 6 7 8 9

Since 6th falls between 5th and 9th, the second element is 5.

Before we find the 3rd element, we must subtract 5 from 6 whose result is 1st combination.

0th

 6 7 8 9

1st

 6 7 8 9

2nd

 6 7 8 9

3rd

 6 7 8 9

From the 1st combination above, we can see that the 3rd element is 7.

Now that all the 3 elements have been found, we have the 91st combination shown below

91th

 0 1 2 3 4 5 6 7 8 9

Let us get back to the problem of knowing the position, given a combination whose elements are side by side.

0th

 0 1 2 3 4 5 6 7 8 9

36th

 0 1 2 3 4 5 6 7 8 9

How do I know the second combination shown above is number 36th? Take a look below:

0th

 0 1 2 3 4 5 6 7 8 9

 0 1 2 3 4 5 6 7 8 9

 0 1 2 3 4 5 6 7 8 9

36th

 0 1 2 3 4 5 6 7 8 9

The combination is 36th, because the total number of combinations of 2 out of 9 is 36. Since this is zero-based, the next combination is the 36th. Let me give you another example!

36th

 0 1 2 3 4 5 6 7 8 9

 0 1 2 3 4 5 6 7 8 9

 0 1 2 3 4 5 6 7 8 9

64th

 0 1 2 3 4 5 6 7 8 9

The combination is 64th, because the total number of combinations of 2 out of 8 is 28 and add 28 to 36, you will get 64.

Combinadic is the method I have just described. You may want to read more about it in the Combinadic wiki because you will find that my explanation and method are different from what is written there. There is a reason for this because I rediscovered this method myself and while writing this section, I found out about Combinadic. Rest assured that my method and Combinadic is actually the same method, merely a different way to get the answer.

A bit of trivia here: I was quite upset that I am not the first one who discovered this method till I stopped writing this article for a year. Well, my reason for inventing this algorithm was to find a method to split the work of finding combinations into different work loads so as to speed up the work on many processors. I found two algorithms, Combinadic and Factoradic, but Combinadic was the first one I found. Later, I found out the algorithm can be modified to find permutation, given its position. I also found out that I am not the first one who discovered Factoradic.

You may have noticed the `CFindCombByIdx` operates on numbers only and the contents of the first combination vector always start from zero and in running numbers. Unlike `next_combination()` which operates on objects by comparing, `CFindCombByIdx` operates on zero based running numbers. What you will get from its results are indexes. For example, you get a result of {0,2,1} out of {0,1,2,3,4}, it means the 1st element is index 0 of array (of objects) you originally want to find combination, 2nd element refers to index 2 of the array and 3rd element is index 1 of the array. Finding combinations of numbers is much easier and faster than finding objects. `CFindCombByIdx` uses a big integer class because this algorithm uses factorials to find the combination and factorials are usually very large numbers. Since it is a templated class and you know the factorials used are not going to exceeded 64 bit, you can use `__int64` type instead. The is the output of the above example code.

Example Code

```   CFindCombByIdx< CFindTotalComb<BigInteger>,
BigInteger > findcomb;

const unsigned int nComb = 3;
const unsigned int nSet = 10;

// Intialize the vector with size nComb
vector<unsigned int> vec(nComb);

// vector returned by FindCombByIdx is the combination at 91.
findcomb.FindCombByIdx( nSet, nComb, 91, vec );```

Below is the timing results of `next_combination`, `CIdxComb` and `CFindCombByIdx` finding combinations of 6 out of 20 elements which is 38760 combinations in total.

```time taken for next_combination: 5.04 milliseconds
time taken for CIdxComb: 0.88 milliseconds
time taken for CFindCombByIdx:  5886.43 milliseconds
```

As you can see, `CFindCombByIdx` is very slow compared to the other 2 algorithms but we are only going to use `CFindCombByIdx` to find the nth combination we want and use `CIdxComb` for finding the rest of the consecutive combinations.

A Benchmark Program for your PC

I have included a demo program called `TimeCombinations` for you to benchmark your PC. It is nice to know how much time has been reduced if you have a dual-core or quad-core PC. The program does not store the combination anywhere and discards them after every computation. If you have a uniprocessor PC, then you have not much use for this benchmark program. Below are the screenshots of the program.

Finding Combinations from a Set with Repeated Elements

Finding combinations from a set with repeated elements is almost the same as finding combinations from a set with no repeated elements: the shifting technique is used and the set needs to be sorted first before applying this technique. It is just that there are some special situations you need to take care of.

Let me used a example of finding combinations of 3 out of 8 {0,1,2,3,3,3,4,5}, the number 3 is repeated 3 times.

With this combination now, the green box is in the 4th column which is 3.

 0 1 2 3 3 3 4 5

If you get this next combination, you need to shift the green box to the last 3, which is the 6th column, before returning this combination result so that the next combination would not be repeated and correct.

 0 1 2 3 3 3 4 5

Another situation to take care of is as below.

 0 1 2 3 3 3 4 5

If you use the combination shifting technique, the next combination would be as below:

 0 1 2 3 3 3 4 5

You need to shift the green box and the blue box to the 5th and 6th column respectively so that the next combination would be correct.

 0 1 2 3 3 3 4 5

There is all you need to know and take care of when finding combinations from a set with repeated elements.

Sample Code for Finding Combinations from a Set with Repeated Elements

Below is the sample. The name of the class used to find the combinations is called `CCombFromRepSet`. As the code is straightforward and commented, I shall not explain the working of the code.

```#include <vector>
#include <iostream>
#include "CombFromRepSet.h"

using namespace std;
using namespace stdcomb;

int main()
{
// Initialize the set
vector<unsigned int> svi;
svi.push_back(0); // 0
svi.push_back(1); // 1
svi.push_back(2); // 2
svi.push_back(3); // 3
svi.push_back(3); // 4
svi.push_back(3); // 5
svi.push_back(4); // 6
svi.push_back(5); // 7

// Object to find the combinations from set with repeated elements
CCombFromRepSet cfrs;
cfrs.SetRepeatSetInfo( svi );

// Set the size of Set and number elements of the combination
const unsigned int SET = 8;
const unsigned int COMB = 3;
cfrs.SetSizes( SET, COMB );

// Initialize the first combination vector
vector<unsigned int> vi;
for( unsigned int j=0; j<COMB; ++j )
vi.push_back( j );

// Set the first combination
cfrs.SetFirstComb( vi );

// Display the first combination
int Cnt=0;
{
cout<<Cnt<<")";
++Cnt;
for( unsigned int i=0; i<vi.size(); ++i)
{
cout<<svi[vi[i]]<<",";
}
cout<<endl;
}

// Find and display the subsequent combinations
while( cfrs.GetNextComb( vi ) )
{
cout<<Cnt<<")";
++Cnt;
for( unsigned int i=0; i<vi.size(); ++i)
{
cout<<svi[vi[i]]<<",";
}
cout<<endl;
}

system( "pause" );

return 0;
}```

This is the output of the sample code:

```0)0,1,2,
1)0,1,3,
2)0,1,4,
3)0,1,5,
4)0,2,3,
5)0,2,4,
6)0,2,5,
7)0,3,3,
8)0,3,4,
9)0,3,5,
10)0,4,5,
11)1,2,3,
12)1,2,4,
13)1,2,5,
14)1,3,3,
15)1,3,4,
16)1,3,5,
17)1,4,5,
18)2,3,3,
19)2,3,4,
20)2,3,5,
21)2,4,5,
22)3,3,3,
23)3,3,4,
24)3,3,5,
25)3,4,5,```

Finding Repeated Combinations from a Set with No Repeated Elements

Now we have come to the last algorithm in the article: finding repeated combinations from a set with no repeated elements! Let me re-iterate again: Combination is the way of picking a different unique smaller sequence from a bigger sequence, without regard to the ordering (positions) of the elements (in the smaller sequence), meaning {0,0,1}, {0,1,0} and {1,0,0} are actually the same combination because they all contain one 1 and two zeros.

The formula for calculating the total number of repeated combinations: (n + r - 1)!/(r!.(n-1)!)

Let me explain, by finding combinations of 3 out 5 {0,1,2,3,4}:

```0,0,0 -> the 1st combination
0,0,1
0,0,2
0,0,3
0,0,4
0,1,1 -> this combination is 0,1,1, not 0,1,0 because we already have 0,0,1.
0,1,2
0,1,3
0,1,4
0,2,2 -> this combination is 0,2,2, not 0,2,0 because we already have 0,0,2.
0,2,3
.
.
0,4,4
1,1,1 -> this combination is 1,1,1, not 1,0,0 because we already have 0,0,1.
1,1,2
1,1,3
1,1,4
1,2,2 -> this combination is 1,2,2, not 1,2,0 because we already have 0,1,2.
.
.
4,4,4 -> Last combination```

As a rule of thumb, when we crossover to the next level in the leftmost column (as you may have noticed from the above explanation), the numbers in rightmost columns always follow the crossover column. For example, the next combination of 0,4,4 is 1,1,1, the first column crossover from 0 to 1, the second and third column follows the first column. Let's give you another example, the next combination of 0,0,4 is 0,1,1, the second column crossover from 0 to 1, third column follows the second column. Remember, when crossover, the minimum number in the rightmost columns after the crossover column follows the crossover column.

Example Code for Finding Combinations from a Set with Repeated Elements

Below is the sample. The name of the function used to find the combinations is called "`CombWithRep`". As the code is straightforward and commented, I shall not explain the working of the code.

```#include <iostream>
#include <vector>
#include <string>
#include "CombWithRep.h"

using namespace std;
using namespace stdcomb;

int main()
{
const int SET = 5;
const int COMB = 3;

// Initialize the first combination vector to zeros
std::vector<unsigned int> vi( COMB, 0 );

// Display the first combination
int Cnt=0;
{
cout<<Cnt<<")";
++Cnt;
for( int j=0; j<COMB; ++j )
{
cout<< vi[j] << ",";
}
cout<<endl;
}
// Find and display the subsequent combinations
while( CombWithRep( SET, COMB, vi ) )
{
cout<<Cnt<<")";
for( int j=0; j<COMB; ++j )
{
cout<< vi[j] << ",";
}
cout<<endl;
++Cnt;
}

cout<<endl;

system( "pause" );

return 0;
}```

This is the output of the example code:

```0)0,0,0,
1)0,0,1,
2)0,0,2,
3)0,0,3,
4)0,0,4,
5)0,1,1,
6)0,1,2,
7)0,1,3,
8)0,1,4,
9)0,2,2,
10)0,2,3,
11)0,2,4,
12)0,3,3,
13)0,3,4,
14)0,4,4,
15)1,1,1,
16)1,1,2,
17)1,1,3,
18)1,1,4,
19)1,2,2,
20)1,2,3,
21)1,2,4,
22)1,3,3,
23)1,3,4,
24)1,4,4,
25)2,2,2,
26)2,2,3,
27)2,2,4,
28)2,3,3,
29)2,3,4,
30)2,4,4,
31)3,3,3,
32)3,3,4,
33)3,4,4,
34)4,4,4,```

Conclusion

We have come to the end of the article. We have covered an optimized algorithm to find non-repeated combinations with integers, an algorithm to find non-repeated combinations, given their index so as to split the work into different work tasks for different processors, an optimized algorithm to finding combinations from a set with repeated elements and lastly, finding repeated combinations. I hope you have found my article useful and easy to understand. I love to hear your feedback, good or bad so that I can improve my article! Thanks!

History

• 7 April 2009 - Updated benchmark source and application
• 12 March 2009 - Changed the source code to use C++ Big Integer Library written by Matt McCutchen, so as to remove the need to download and build Crypto++, and also to reduce download sizes.
• 17 Nov 2007 - First release

Share

Software Developer
Singapore
No Biography provided

 First Prev Next
 inverse relationship Andrea Gaetan 6-Nov-13 0:11
 Re: inverse relationship Wong Shao Voon 7-Nov-13 2:01
 Re: inverse relationship Andrea Gaetan 7-Nov-13 4:34
 Re: inverse relationship Wong Shao Voon 7-Nov-13 22:20
 Re: inverse relationship Andrea Gaetan 7-Nov-13 23:03
 Re: inverse relationship Wong Shao Voon 8-Nov-13 20:49
 Re: inverse relationship Andrea Gaetan 8-Nov-13 22:17
 Ratio Reduction Theory Member 10145265 8-Jul-13 4:27
 Wong Shao Voon hello, I'm Andrea from Italy. I apologize for my English, I had to use a translator. I hope you can understand the same. I wanted to compliment you on the Treaty "Combinations in C + +, Part 2." I found it very useful even if it took me a long time to figure it out. I am a self-taught programmer, I have not had the chance to study a lot. I know a little '"Pascal / Delphi" and I was able to apply "The Technique of Finding Combination, Given its Index" with stunning results. Again, thank you. I wanted to take advantage of the situation to ask a help to the problem that now I am going to exhibit. In Italy there is a game called Lotto extractions. Are extracted 6 numbers out of 90 for a total of 622,614,630 possible combinations. These combinations of numbers taken 6a6. (Example combinations (9,6) = 84) with 9 numbers that you create 84 combinations. Cn,k = n! / k! (n-k)! I'm trying to find a reduced system, so select the smallest possible number of combinations able to represent the standard deviation of 1 point (n-1, reduced warranty for Lotto 5) or the standard deviation of 2 points (n-2, double reduced warranty 4 for Lotto) or the standard deviation of 3 points (n-3, triple reduced warranty for 3 Lotto) all combinations of the relative integral system (Example combinations (9.6) or combination (20.6) or combination (51.6) ...). (Ratio Reduction Theory) RRT = gr * ( n - gr ) + 1 9! / 6! (9-6)! = 362.880 / (720 * 6) = 84 RRT = 6 * ( 9 - 6 ) + 1 = 19 84 / 19 = 4,42 rounded 5 Let me explain. If I play an integral system of 10 numbers I have a development of 210 combinations 6a6. To have the confidence to make 6 I have to play all 210 combinations. But if I'm happy to do 5, then I reduce significantly the number of combinations to be taken into account. The "firsts reduction" of 10 numbers to guarantee 5 is 14. The "firsts reduction" of 10 numbers to guarantee 4 is 3. So divided. complete 210 1.2.3.4.5.6 1.2.3.4.5.7 1.2.3.4.5.8 1.2.3.4.5.9 1.2.3.4.5.10 1.2.3.4.6.7 …. …. 5.6.7.8.9.10 warranty 5 1.2.3.4.9.10 1.2.3.5.8.9 1.2.3.6.8.10 1.2.4.7.8.9 1.2.5.6.7.10 1.3.4.5.6.9 1.3.4.5.7.8 1.4.5.7.9.10 1.6.7.8.9.10 2.3.4.6.7.10 2.3.5.6.7.9 2.4.5.6.8.10 3.4.6.7.8.9 3.5.7.8.9.10 warranty 4 1.2.3.8.9.10 1.2.4.5.6.7 3.4.5.6.8.9 For a long time I'm looking for and studying a method to obtain these reductions. But it must be a quick and powerful way, because the one I use does not work well and is very slow especially when using more than 10 numbers. I noticed that changing the order of choice, the number decreases. Do you wonder if you can develop a method for me much better performance than what I did, so then I do it in pascal / delphi. The method I use is this ... I write the code that I use in Delphi because it is too complicated to explain. I hope for you is understandable. My algorithm works as follows: in nested for loops create the integral of all possible combinations for numeridaelaborare ... and the comparison with the variabilearray to see if the sextuplets stored there covering the sequence that I create in the nested for loops ... if the sequence is not covered, then increase variabilearray sequence is not covered ... and resume to loop in nested for ... until the end ... then memorize the sequence of variabilearray found in a database table. The method described below is very simple but it gives excellent results in terms of reduction ... however, is always a good starting point to develop best reduced. NB the numbers are processed in sequence x facilitate the understanding of the algorithm. procedure TForm1.classicoClick(Sender: TObject); type Tarraygrid = array of array of integer; // define the type of array var // define the variables tiporiduzione : smallint; numeridaelaborare,et1,et2,et3,et4,et5,et6,i,riga,colonna,primogiro,f,avacont,quanterighe : integer; variabilearray : tarraygrid; label salto; begin // identify the type of reduction warranty if riduzionen1.Checked = true then tiporiduzione := 5; if riduzionen2.Checked = true then tiporiduzione := 4; if riduzionen3.Checked = true then tiporiduzione := 3; // I choose to work out how many numbers the reduction numeridaelaborare := strtoint(numriduzionidaelaborare.Text); // numbers to be processed // creates arrays for primates 1 row and 6 columns SetLength(variabilearray,1,6); // processing procedure REDUCED primogiro := 0; quanterighe := 1; // nested for loops I create all possible combinations for numeridaelaborare (eg 10 I 210 number combinations) for et1 := 1 to numeridaelaborare - 5 do begin for et2 := et1 + 1 to numeridaelaborare - 4 do begin for et3 := et2 + 1 to numeridaelaborare - 3 do begin for et4 := et3 + 1 to numeridaelaborare - 2 do begin for et5 := et4 + 1 to numeridaelaborare - 1 do begin for et6 := et5 + 1 to numeridaelaborare do begin avantiquante := 0; for riga := 0 to quanterighe - 1 do begin avacont := 0; for colonna := 0 to 5 do begin if (et1 = variabilearray[riga,colonna]) or (et2 = variabilearray[riga,colonna]) or (et3 = variabilearray[riga,colonna]) or (et4 = variabilearray[riga,colonna]) or (et5 = variabilearray[riga,colonna]) or (et6 = variabilearray[riga,colonna]) then begin inc(avacont); end; end; if avacont >= tiporiduzione then begin inc(avantiquante); end; end; if avantiquante = 0 then begin if primogiro > 0 then begin inc( quanterighe); // increase the capacity of the array to add a new combinations SetLength(variabilearray,quanterighe,6); end; // the people array of records found variabilearray[quanterighe-1,0] := et1; variabilearray[quanterighe-1,1] := et2; variabilearray[quanterighe-1,2] := et3; variabilearray[quanterighe-1,3] := et4; variabilearray[quanterighe-1,4] := et5; variabilearray[quanterighe-1,5] := et6; primogiro := 1; end; end; end; end; end; end; end; // end nested for loops // END processing procedure REDUCED // writes to the database f := 0; for i := 0 to high(variabilearray) do begin with dbf2 do begin append; f := f + 1; Fields[0].asinteger := variabilearray[i,0]; Fields[1].asinteger := variabilearray[i,1]; Fields[2].asinteger := variabilearray[i,2]; Fields[3].asinteger := variabilearray[i,3]; Fields[4].asinteger := variabilearray[i,4]; Fields[5].asinteger := variabilearray[i,5]; post; end; end; // end for // end of write to the database end; I hope you understand my problem, and I hope you can help me. I apologize if I have dwelt too. I really hope not to give too much trouble. Many thanks again for the time you can devote Andrea G. Italy
 My vote of 5 Member 10145265 8-Jul-13 4:09
 Great article with clear explanations and diagrams Defenestration 2-Apr-12 10:10
 My vote of 5 Member 7936304 18-May-11 22:29
 most efficient way to store results? kadekade 9-Apr-09 3:09
 Re: most efficient way to store results? Shao Voon Wong 12-Apr-09 16:14
 Re: most efficient way to store results? kadekade 14-Apr-09 0:46
 Re: most efficient way to store results? Shao Voon Wong 14-Apr-09 16:17
 Very nice! Hans Dietrich 18-Mar-09 23:29
 Re: Very nice! Wong Shao Voon 19-Mar-09 4:54
 I have visual studio 6.0 bozaboza 3-Mar-09 2:53
 Re: I have visual studio 6.0 Wong Shao Voon 3-Mar-09 21:12
 Re: I have visual studio 6.0 kadekade 4-Mar-09 2:09
 Re: I have visual studio 6.0 Wong Shao Voon 4-Mar-09 19:03
 Re: I have visual studio 6.0 Wong Shao Voon 8-Mar-09 15:52
 Re: I have visual studio 6.0 kadekade 10-Mar-09 21:17
 wish i had a vb or better yet assembly example nickhere 12-Aug-08 7:44
 Re: wish i had a vb or better yet assembly example CBasicNet 24-Aug-08 23:01
 Where I learn about Combinadics and Factoradics Wong Shao Voon 7-May-08 16:55
 Combinatorial Algorithms reference Mr. X B 21-Nov-07 8:58
 Re: Combinatorial Algorithms reference Wong Shao Voon 25-Nov-07 20:40
 Last Visit: 31-Dec-99 19:00     Last Update: 18-Apr-15 7:17 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.