Click here to Skip to main content
15,899,825 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello,
In my project I am trying to get all combination between 2 numbers, for example if I have 2 array the first one store the min bound and the second one store the max bound,so arr1[3] = {1,1,2} and the arr2 = {2,2,3} so I should build a 2d array store all combination which are
112, 212, 122, 222, 113, ..., 223.
first I calculate the number of row of the 2d array and since the number of element of min and max are vary between 10 and 20, it sometime give me a large number which need to build a huge array, my code is:
C++
unsigned long long row =0;  // to count the number of row
unsigned long long rh1 = 1;

for(int i=0; i<col;++i)    {
rh1 *= t_end[i] - t_s[i] + 1;// t_end is max bound array, t_s is the min bound arr
row += rh1;

 cout << "Row= "<< row <<endl;
  }


so some time the number (row) become so large and can't handle this value, for example if I have the following min and max bound:
t_s = {3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 }
t_end = {2 2 3 4 6 10 3 11 11 13 4 15 8 9 19 19 20 23 27 10 }

then the row will be as follow:
VB
Row= 4
  Row= 32
  Row= 144
  Row= 1152
  Row= 11232
  Row= 112032
  Row= 1120032
  Row= 14224032
  Row= 92848032
  Row= 1193584032
  Row= 16603888032
  Row= 309399664032
  Row= 2944561648032
  Row= 53012639344032
  Row= 1104442270960032
  Row= 24235894166512032
  Row= 278681865017584032
  Row= 6894277107145456032
  Row= 12879056739084163488
  Row= 5417061573465168288     --- this value is smaller than previous and this is wrong


and sometime the Row value become negative, so how to solve this issue, and for of course I cant build an array with this huge number of row, and I was thinking to divide it, but I can't get the number of row that allow me to calculate the number of sub-array I should have.
Other question, what is the max size of array that I could have and how to know that.
Posted
Updated 10-Oct-11 11:37am
v3
Comments
Stefan_Lang 11-Oct-11 8:56am    
Your results don't match your example and algorithm: The first output equates to 0+((2-3+1)*1 and that is 0, not 4. To get a resolt of 4 the max value must be 4 bigger than the min value, but it's smaller! Even after fixing that, the second value equates to 4+(2-2+1)*4 = 8, and not 32. I didn't bother to check the follow-up values...

12879056739084163488 is a very big number, your next iteration wraps around the size limit of an unsigned long long, causing the smaller number.

[Update]
You can try Matt McCutchens' C++ Big Integer Library[^]

Best regards
Espen Harlinn
 
Share this answer
 
v2
Comments
sami984 11-Oct-11 5:24am    
Yes, I know that, but how to solve this problem? how to handle such a big number?
Use an arbitrary-precision math[^] class, for example GMP[^].
 
Share this answer
 
Comments
Espen Harlinn 11-Oct-11 18:25pm    
GMP is quite good, my 5
I think there's something intrinsically wrong in your algorithm, depending on what your actual problem is: either you are talking about arrays of values, or you're talking about digits of numbers. The example that causes your problem indicates that you are not, actually talking about digits of (potentially very long) numbers at all, since some of the max values are not digits at all!

So why are you converting these arrays of numbers into a big integer number? Just stick with arrays of numbers, just like you defined your min and max array! Problem solved.

P.S.: I just noticed you even said that you need to define a 2D array to store all intermediate combinations, so your requirement is, after all, to produce a list of arrays of numbers, not a list of very long numbers!
 
Share this answer
 
v2
Comments
sami984 11-Oct-11 8:04am    
I am talking about array of values, so when I said the min. number is 112 i meant the element of min. array is 1,1,2 and so on.
I am trying to compute how many row that the 2d array which will store all combination between the min. and max. arrays. In my algorithm which I post I just put the code which generate the number of row which I will use it later to generate the combination of numbers between these values. I need the row value for my later "for loop".
hope this is clear.
I will put the example again
if min array {1,1,2} and max array is {2,2,3} the the my 2d array will be as following
{{1,1,2},
{2,1,2},
{1,2,2},
{2,2,2},
{1,1,3},
...,
{2,2,3}}
Stefan_Lang 11-Oct-11 8:15am    
I just put the code which generate the number of row which I will use it later
That is the part that confuses me. Why can't you just generate the next row and store it? You didn't mention a requirement to somehow generate a 'key', nor that this 'key' should allow you to reconstruct the row that it represents. Are these actual requirements or did you only introduce them because you thought you needed it?

I think you are overcomplicating the issue, and anyway, your method of generating a 'key' breaks down the moment you deal with 'digits' greater than 9, because you can no longer determine the original sequence of numbers when you do not know how many digits belong to each number in a sequence.

P.S.: (cut the example because it doesn't match your algorithm)
I just realized one more thing: you cannot possibly mean to store all possible combinations! For one it wouldn't make sense because the 'min' and 'max' arrays fully describe them, and second you don't have that much storage! (by a very rough estimation you're trying to store 2*10^21 bytes of data, that's roughly 2000 million Terabytes!)

Is your intention, then, to generate a unique key for a given sequence that you can use to later generate it? Or if not that, what else is the point of all this?
sami984 11-Oct-11 9:21am    
mmmmmmmmmm yes I think you are right, I just complicate my self by the number of row, while I can just check the max. boundary :) thank you :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900