Cannot understand what's wrong here...

[TheIdeasMan]

vector<int> coll1;

same problem with this one.

Make sure that n is 20 max as well, to limit the for loops.

[TheIdeasMan]

Also try to use the debugger to track your variables to see where they go wrong.

[jumper007]

Ok, now it looks like this, but still got error.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int factorial(int n)
{
	if (n == 0)
		return 1;
	else
		if(n == 1)
			return 1;
		else
			return n*factorial(n-1);
}
int main()
{
	int n, cnt, case_nr, SOP1, SOP2;
	vector<int> P (20,0);
	vector<int> SOP (20,0);
	vector<int> coll1 (20,0);
	
	case_nr = 1;
	
	do
	{
		cin >> n;
		
		cnt = 1;
		
		if (n == 0)
			break;
		
		for (int c = 0; c < n; c++)
			coll1.push_back(c);
		
		SOP1 = 0;
		for (int i = 0; i < n; i++)
		{
			P[i+1] = coll1[i] * coll1[i+1];
			SOP1 = SOP1 + P[i+1];
		}
		SOP1 = SOP1 + (coll1[0] * coll1[n-1]);
		
		for (int j = 1; j <= factorial(n); j++)
		{
			SOP[j-1] = SOP1;
			
			next_permutation(coll1.begin(), coll1.end());
			
			SOP2 = 0;
			
			for (int i = 0; i < n; i++)
			{
				P[i+1] = coll1[i] * coll1[i+1];
				SOP2 = SOP2 + P[i+1];
			}
			SOP2 = SOP2 + (coll1[0] * coll1[n-1]);
			
			SOP[j] = SOP2;
		}
		
		for (int k = 0; k < factorial(n); k++)
		{
			vector<int> coll2 (n,0);
			
			unique_copy (coll1.begin(), coll1.end(), coll2.begin());
			
			if (coll2[k] != coll2[k+1])
				cnt++;
		}
		
		cout << "Case #" << case_nr << ": " << cnt << endl;
		
		coll1.clear();
		
		case_nr++;
	}while (n != 0);
	
	return 0;
}

I insert '3' it returns '7' (instead of '1'), after, I insert '4', and it crashes. (terminated with Runtime error code 3)

EDIT: Okay. I'll try with the debuger.

[jumper007]

No change of solving it... My debugger sends me in endless libraries instead of changing variables values stl_vector.h stl_iterator.h vector.tcc new_allocator.h iostream stl_uninitialized.h stl_algobase.h stl_construct.h new stl_algo.h stl_iterator_base_types.h, and so on...

The code is:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int factorial(int n)
{
	if (n == 0)
		return 1;
	else
		if(n == 1)
			return 1;
		else
			return n*factorial(n-1);
}
int main()
{
	int n, cnt, case_nr, SOP1, SOP2;
	vector<int> P (20,0);
	vector<int> SOP (20,0);
	vector<int> coll1 (20,0);
	
	case_nr = 1;
	
	do
	{
		cin >> n;
		
		cnt = 1;
		
		if (n == 0)
			break;
		
		for (int c = 0; c < n; c++)
			coll1.push_back(c);
		
		SOP1 = 0;
		for (int i = 0; i < n; i++)
		{
			P[i+1] = coll1[i] * coll1[i+1];
			SOP1 = SOP1 + P[i+1];
		}
		SOP1 = SOP1 + (coll1[0] * coll1[n-1]);
		
		for (int j = 1; j <= factorial(n); j++)
		{
			SOP[j-1] = SOP1;
			
			next_permutation(coll1.begin(), coll1.end());
			
			SOP2 = 0;
			
			for (int i = 0; i < n; i++)
			{
				P[i+1] = coll1[i] * coll1[i+1];
				SOP2 = SOP2 + P[i+1];
			}
			SOP2 = SOP2 + (coll1[0] * coll1[n-1]);
			
			SOP[j] = SOP2;
		}
		

		// I am sure this is the problem. I am trying to find out how many different values there are in the vector, but I can't seem to find the right way of doing it :/
		for (int k = 0; k < factorial(n); k++)
		{			
			vector<int>::iterator it;
			
			it = unique (coll1.begin(), coll1.end());
			
			coll1.resize( it - coll1.begin() ); 
			
			if (coll1[k] != coll1[k+1])
				cnt++;
		}
		
		cout << "Case #" << case_nr << ": " << cnt << endl;
		
		coll1.clear();
		
		case_nr++;
	}while (n != 0);
	
	return 0;
}

[viliml]

int count_unique(vector<int> a)
{
      return std::unique(a.begin(), a.end())-a.begin();
      }

[TheIdeasMan]

My debugger sends me in endless libraries instead of changing variables values

I am not sure what debugger you have, usually you create a watch list of varibles, then step through the code. You can use step over, to avoid disappearing into libraries. You can also set breakpoints.

Apart from this, maybe it would be worthwhile to do a design for your code.

This can be acheived by writing comments that describe each step in your methodology. The comments can be done incrementally, start with very general ideas then go back and fill more detail. This can be repeated until you have a full description. Doing this helps to organise your ideas logically, helps with deciding what functions to have, and helps to produce clear understandable organised code.

You then go back and write the code that does what's in each of the comments. Leave the comments there as they act as documentation.

This might sound boring, and you may not want to abandon the code you have beacuse of the time spent on it so far, but it really could be worthwhile, and you may be surprised at the results.

Check out the "loops" thread by SGM3. There are over 100 posts (6 pages worth), you can see what we started with, all the drama's we had, and right at the end something close to a result, which in my opinion was much better than what we started with. I just wish that I had mentioned the idea of doing a design much earlier, rather than have over 100 posts.

I am not having a go at SGM here, (he appreciates that I helped him quite a lot) , everyone starts somewhere.

I have mentioned all this because it may help you to becaome a better coder.

[TheIdeasMan]

Hi jumper007,

I may have been a bit quick of the mark with some of the things in my last post. It was my bad that I didn't read & understand the problem properly, now that I have your code code makes more sense now.

However, my suggestion of doing a design might still be of some use, I have the following questions / observations:

A <vector> is really a static (ie not dynamic) array of pointers to objects. In other words it is like a C array of pointers that cannot be resized. When you resize a vector, the compiler reallocates a brand new array that is big enough. You can make the array large enough in the first place for the worst case scenario, but this is often a waste. So a vector is really only good for things that you know are not going to change at all, or rarely.

A <list> is a double linked list of pointers to objects that is much more efficient for increasing the size.

This is important because you are resizing coll1 factorial(n) times.

Now back to the size of a factorial:

factorial(20) is 2.4329E+18, so an unsigned long long will just hold this value.

This also means that your loops are going to execute 2.4329E+18 times, making it easy to get a stack overflow, or fill up the memory. It also means the vector size of 20 is now a problem - 20 was the number of cases, but you need a vector that has factorial(n) elements. I now see why you had the large value yesterday.

I find the question a bit strange that they require you to go to this limit. factorial(7) is 5040, I would have thought that would have been enough.

I guess this means that you may have to come up with a way of doing this without storing everything in a vector. Might have to google some algorithms for doing this eficiently.

The other problem is with the for loops:

for (int i = 0; i < n; i++)
			{
				P[i+1] = coll1[i] * coll1[i+1];
				SOP2 = SOP2 + P[i+1];
			}

the i+1 will go past the end of the vectors.

Have you tested your factorial function independently? Normally with recursion you have to have a base case that causes the recursiion to end, in this case it is n==1. You are decrementing n, so when n is 1 it returns 1, so the function always returns 1. Let me know if I have gone totally mad and what I am saying is wrong !!!

int factorial(int n)
{
	if (n == 0)
		return 1;
	else
		if(n == 1)
			return 1;
		else
			return n*factorial(n-1);
}

In main, you have a do loop that tests n != 0, but I don't see where you decrement n, in fact it is re-entered by the user at the start of the do loop. May be this could be better with a for loop using a different variable.

The next_permutation function returns a bool, you should test this just in case, it will be false if the iterator returns to the beginning.

Some other improvements, would be better meaningful variable names (not single letters). I know you have used names like SOP because that was what was in the question - If it was me I would use SumOfProduct.

Comments are really helpful for others to understand your code, you could put them in before the for loops to explain what they do. Also comment the variables when you declare and initialise them, & put all these with 1 variable per line.

Hope this helps, sorry for leading you astray yesterday, I hope I have made up for it with today's comments.

[Peter87]

TheIdeasMan wrote:

A <vector> is really a static (ie not dynamic) array of pointers to objects. In other words it is like a C array of pointers that cannot be resized. When you resize a vector, the compiler reallocates a brand new array that is big enough. You can make the array large enough in the first place for the worst case scenario, but this is often a waste. So a vector is really only good for things that you know are not going to change at all, or rarely.

A vector is not an array of pointers. Only if you store pointers in it (like std::vector<int*>) it would contain an array of pointers. You can get the size of the internal array by using the capacity() member function. When it has to reallocate, it doesn't just increase the capacity by one. A common strategy is to double the capacity, so it doesn't have to reallocate very often. With this strategy it only has to reallocate 21 times if you insert 1000000 elements. That makes adding elements to vector quite efficient as long as the elements are added to the end.

TheIdeasMan wrote:

A <list> is a double linked list of pointers to objects that is much more efficient for increasing the size.

The overhead of std::list is often bigger than the overhead of std::vector. At least for elements that are cheap to copy/move.

[TheIdeasMan]

Peter87 wrote:

A vector is not an array of pointers.

TheIdeasMan wrote:

array of pointers to objects.

Ok, I see what you are saying but I am wondering how a vector of class objects is implemented? Is this not an array of pointers to the objects? I guess it just stored contiguously.

With the reallocation, I found this on wiki:

When new elements are inserted, if the new size of the vector becomes larger than its capacity, reallocation occurs.[1][4] This typically causes the vector to allocate a new region of storage, move the previously held elements to the new region of storage, and free the old region.

I thought this was a problem for the OP because he was reallocating every time in the loop.

I see what you are saying about the list overhead.

[ne555]

I guess it just stored contiguously.

Yep, that's the idea.
To handle class without a default constructor, placement new is used (encapsulated in an allocator class)

[TheIdeasMan]

Jumper007,

I had some more thoughts:

Instead of storing factorial(n) number of SumProducts in a vector, why not test whether a SumProduct is already in the vector (use find algorithm) and only store it if it isn't there, that way the vector can be of length 30 as per the question, and the vector will be a unique set of values.

There is still the problem of the loop executing up to 2.4329E+18 times.

[TheIdeasMan]

@ne555,

I guess I am used to dealing with reasonably large objects, so I have always used pointers.