C++

Forum

 
Array problem

equinoX (19)
Hello Guys,

Here is the situation, I found a very fast code which generates combinations of a given size and range in the following link: http://snippets.dzone.com/posts/show/4666

Then I made a little modification to generate the combinations represented by bits using the bitset library:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include<bitset>
bitset<32> bitcombs;

void printcomb(int comb[], int k)

{

       bitcombs.reset();
				
	for (int i = 0; i < k; ++i)  {

	           bitcombs.set((comb[i] + 1) - 1 ,true);
	    }

       cout << bitcombs << endl;

}


It's working perfectly too, but I'm needing to store the combinations generated into an array, so I declared a global int array and an int counter to be the indexer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include<bitset>
int counter = 0;
int CombArray[];
bitset<32> bitcombs;

void printcomb(int comb[], int k)

{

       bitcombs.reset();
				
	for (int i = 0; i < k; ++i)  {

	           bitcombs.set((comb[i] + 1) - 1 ,true);
	    }

         CombArray[counter] = bitcombs.to_ulong();
         counter++;

}


But I'm getting two errors during the compilation:

Combin.obj : error LNK2001: unresolved external symbol "int * CombArray" (?CombArray@@3PAHA)
Release/Combin.exe : fatal error LNK1120: 1 unresolved externals

And I really don't know what I'm doing wrong, do you know where these errors come from? Do I need to ReDim the array before the process? I did it, but the errors remains the same...

Regards,
equinoX
DrChill (574)
me:*gripe* *grumble* *gripe*

Anyway, what line of code is it erroring.
Disch (13742)
(comb[i] + 1) - 1

Umm.. what? Why add 1 only to immediately subtract it? Why not just use comb[i]?

Anyway... This looks like your problem:

int CombArray[];

I'm surprised that compiles at all. You can't have a sizeless array like that unless you give it initialization data (ie: int CombArray[] = {1,2,3,4};, in which case the size of the array can be determined)

It looks like you want this array to grow dynamically, which sounds like you want to use a vector/deque:

1
2
3
4
5
6
7
8
 
vector<int> CombArray;

void printcomb(int comb[], int k)
{
         // ...
         CombArray.push_back( bitcombs.to_ulong() );

}
jsmith (5804)
You should also know that bitset's operations are all bounds checked, so set() is indeed not nearly as fast
as it could be if you used the unchecked version of set().
blackcoder41 (1426)
Umm.. what? Why add 1 only to immediately subtract it? Why not just use comb[i]?
hahaha! that was funny.. lmfao.. no offence
Last edited on
equinoX (19)
Hey guys, thanks for the assist

DrChill, these are the errors:

Combin.obj : error LNK2001: unresolved external symbol "int * CombArray" (?CombArray@@3PAHA)
Release/Combin.exe : fatal error LNK1120: 1 unresolved externals

Disch, you are right about to add and to subtract one, there is no sense do to it, my mistake :]

You know, I'm coming from VB where the array manipulations is much more simplier and I still did not get clearly how it works in C++. I thought to resize the CombArray in the void main with the exact number of elements of the total of the combinations before the combs generation (as we do in VB), but the errors keeps the same, but anyway, I will try your suggestion of the vector.

jsmith, I did not understand your recommendation, can you give the code sample of how I should code?

Guys, thanks once again, I will post the whole code here and you can copy and paste to see what's going on. I sure that the problem is quite simple, but as I started with C++ 2 weeks ago, I don't know how to debug it :D

Regards,
equinoX
equinoX (19)
blackcoder


Umm.. what? Why add 1 only to immediately subtract it? Why not just use comb[i]?
hahaha! that was funny.. lmfao.. no offence


The original code prints comb[i] + 1 to print 1,2,3,4,5... otherwise it will print 0,1,2,3,4
Then I did this: bitcombs.set((comb[i] + 1) ,true), but I forgot that the Lbound of the bitset starts at 0 too, then I did: bitcombs.set((comb[i] + 1) -1 ,true), but much much simplier would be just comb[i]

Don't tell me that you never wrote a redundant code in your lifetime?

equinoX (19)
Here is the complete code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 

#include <iostream>
#include <bitset>

using namespace std;

int n;
int k;

int counter = 0;
int CombArray[];

bitset<32> bitcombs;

void printcomb(int comb[], int r);
bool next_combination(int comb[], int r, int n);
double factorial (int x);
int getcombinations (int n, int k);

void main(int argc, char *argv[]) 

	{

		cout << "Input N value: ";
		cin >> n;

		cout << "Input K value: ";
		cin >> k;

		cout << endl;

		if (k < n)

			{
				int comb[31]; // is possible to resize comb[k] ?
				// CombArray[getcombinations(n,k)];

				for (int i = 0; i < k; ++i)
					comb[i] = i;
					printcomb(comb, k); 

				while (next_combination(comb, k, n))

					{
						printcomb(comb, k);
					}
		
				cout << endl;
				cout << getcombinations(n,k) << " generated" << endl;


			}

		else 
			
			{
				cout << "Invalid parameters" << endl;
				cin.get();
			}


	}


void printcomb(int comb[], int r) 

	{

		bitcombs.reset();
				
			for (int i = 0; i < k; ++i)

				{
					bitcombs.set(comb[i],true);
				}

			//cout << bitcombs.to_ulong() << endl;
			//CombArray[counter] =  bitcombs.to_ulong();


	}


bool next_combination(int comb[], int k, int n) 

	{

		int i = k - 1;
		++comb[i];
		
			while ((i >= 0) && (comb[i] >= n - k + 1 + i))
	
				{
					--i;
					++comb[i];
				}

			if (comb[0] > n - k) 
			
			return false; 

	
			for (i = i + 1; i < k; ++i)

				{
					comb[i] = comb[i - 1] + 1;
				}

			return true;

	}


double factorial (int x) 

	{

		double j = 1;

			for (int i = 2; i <= x; i++)

				{
					j = j * i;
				}

		return j;

	}


int getcombinations (int n, int k)

	{	
		double nFac;
		double kFac;
		double nkFac;

		nFac = factorial(n);
		kFac = factorial(k);
		nkFac = factorial(n - k);

		return nFac / (kFac * nkFac);

	}
equinoX (19)
Forgot one line:

1
2
3
4
 

//CombArray[counter] =  bitcombs.to_ulong();
//counter++;
equinoX (19)
one more correction:

1
2
 
void printcomb(int comb[], int r);
bool next_combination(int comb[], int r, int n);


should be:

1
2
 
void printcomb(int comb[], int k);
bool next_combination(int comb[], int k, int n);


just replace "r" by "k", but it's working anyway ;]
Disch (13742)
I thought to resize the CombArray in the void main with the exact number of elements of the total of the combinations before the combs generation (as we do in VB)


Well first off, you can't have void main. main should always return an int (even though some compilers let you get away with void main, you shouldn't do it).

Secondly, you can't resize arrays. If the array size cannot be determined at compile time (ie: it depends on user input or changes as the program runs), you have two options:

1) dynamically allocate the array with new[] (and remember to free the memory with delete[])
or
2) use a vector (as I tried to show in my previous post)


Vectors are basically resizable arrays. See this reference page: http://cplusplus.com/reference/stl/vector/

Pretty much, instead of making an array, you'd make a vector:

1
2
3
 
//int CombArray[];  // BAD, doesn't work

vector<int> CombArray;  // good


A few functions to know about:

- size() gets you the number of elements in the vector, so you don't need to keep track of it seperately
- resize() allows you to explicitly set the size of the array
- push_back() let's you add a new element to the end of the array, increasing the size by 1
- pop_back() drops the last element in the array (decreasing the size by 1)

Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
vector<int> foo;

foo.resize(3);  // make the size of the array 3

foo[0] = 0;  // you can then use the [] operator just like a normal array
foo[1] = 1;
foo[2] = 2;

foo.push_back(3);  // increase the size by 1, putting the number '3' at the end of the array

cout << foo.size() << "\n";  // prints "4"

// print all elements in the vector:
for(unsigned i = 0; i < foo.size(); ++i)
    cout << foo[i];

// prints "0123"
equinoX (19)
Thanks Disch,

I did not know about the void main stuff, I'm using VC++ 6.0 and it's compiling without any error, that's why I'm doing this way, thanks for the tip.

And as I'm seeing, vectors fits perfectly on what I'm trying to do. The problem was: I was trying to make in C++ what we make in VB ;]

Thank you Disch, problem solved
Regards
Disch (13742)
I'm using VC++ 6.0


You need to upgrade. That's over a decade old. C++ has changed in that time.

You can get a new version of VC++ from microsoft's site for free. I highly recommend you get it.
equinoX (19)
Yes, in fact I have both versions installed here, but the 2010 version is too heavy to my machine - p4 3.2 ghz, need to udgrade my machine first.

One question Disch, do you know if the guys of the boost.org developed an enhanced bitset library?
Topic archived. No new replies allowed.