Counting to n, how many different summations

Get n from the user, use recursion

Page 1 of 1

13 Replies - 742 Views - Last Post: 28 August 2009 - 09:17 PM Rate Topic: -----

#1 jheld  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 04-May 09

Counting to n, how many different summations

Post icon  Posted 24 August 2009 - 03:15 PM

#include <iostream>
using namespace std;

int count(int n, int counter, int n1)
{
	if(n ==2)
		return counter;
	int base_n = 1, sum;
	else
	  {
		 sum += n1;
		 if(sum <= n)
			 count(n, counter++, n1++);
  

	 }


}


int main()
{
		int n, int counter = 1, n1 = 1;
	cout << "enter n (greater than or equal to 2): ";
   cin >> n;
 
  cout << count(n, counter, n1);

return 0;
}







I am trying to get a head start on my lab, but it has been awhile since I've done any C++ programming. Hoping that someone can help guide me in the right direction for the recursive design.

Is This A Good Question/Topic? 0
  • +

Replies To: Counting to n, how many different summations

#2 OliveOyl3471  Icon User is offline

  • Everybody's crazy but me!
  • member icon

Reputation: 134
  • View blog
  • Posts: 6,581
  • Joined: 11-July 07

Re: Counting to n, how many different summations

Posted 24 August 2009 - 04:38 PM

This is kind of a common topic here. If you do a search of the site, I am sure you can find what you're looking for.

Here's one code snippet that may help:
http://www.dreaminco.../snippet667.htm
Was This Post Helpful? 0
  • +
  • -

#3 jheld  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 04-May 09

Re: Counting to n, how many different summations

Posted 26 August 2009 - 11:00 AM

View PostOliveOyl3471, on 24 Aug, 2009 - 03:38 PM, said:

This is kind of a common topic here. If you do a search of the site, I am sure you can find what you're looking for.

Here's one code snippet that may help:
http://www.dreaminco.../snippet667.htm


#include <iostream>
using namespace std;

//FUNCTION DECLARATION
int count_permutations(int n);

int count_no_permutations(int n);




int main()
{
	char choice;
	do
	{
		int n;
		cout << "Please enter an integer: ";
		cin >> n;
		while(n < 2)
		{
			cout << "Please enter an integer greater than or equal to 2: ";
			cin >> n;
		}
		cout << "The number of summations with permutations is " << count_permutations(n) << endl;
		cout << "The number of summations without permutations is " << count_no_permutations(n) << endl;
		cout << "Would you like to enter another integer? (y/n) ";
		cin >> choice;
		while(choice != 'y' && choice != 'n')
		{
			cout << "Press 'y' or 'n': ";
			cin >> choice;
		}
	}while(choice == 'y');
	return 0;
}

//FUNCTION DEFINITION
int count_permutations(int n)
{
	//Base Case for the recursive function
	if(n == 2)
		return 1;
	int counter = 1;
	
	for(int n1 = n - 1; n1 > 1; n1--)
	{
		counter++;
		if(n1 >= 2)	
			counter += count_permutations(n1);
	}
	return counter;	
}

int count_no_permutations(int n)
{
	//Base Case for the recursive function
	if(n == 2)
		return 1;
	int counter = 1;
	
	for(int n1 = n - 1; n1 > 1; n1--)
	{
		int n2 = n - n1;
		counter++;
		if(n1 == n2)
			counter += count_no_permutations(n1) + count_no_permutations(n2);
	}
	return counter;
}





Well, the other topic didn't really help. They were different problems, to say the least. But, I have completed the first half of the lab...the second part, which deals with not counting permutations together (e.g. (1,1,2) and (1,2,1) and (2,1,1) all three times), I have been unable to figure out.
Was This Post Helpful? 0
  • +
  • -

#4 Locke  Icon User is offline

  • Sarcasm Extraordinaire!
  • member icon

Reputation: 521
  • View blog
  • Posts: 5,596
  • Joined: 20-March 08

Re: Counting to n, how many different summations

Posted 26 August 2009 - 11:06 AM

jheld...hm...a username I've seen before. The guy that showed me g.ho.st.

Hello there!

This assignment is SUSPICIOUSLY similar to mine (not the code, the assignment)...probably because he's in the same class. EECS 268, correct? Lab assignment #1? :D

(if you don't know who I am...click my name, it'll tell you ;))

This post has been edited by Locke: 26 August 2009 - 11:09 AM

Was This Post Helpful? 0
  • +
  • -

#5 jheld  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 04-May 09

Re: Counting to n, how many different summations

Posted 28 August 2009 - 02:04 PM

int n, min = 1;

int count_no_permutations(int n, int min)
{
	//Base Case for the recursive function
	if(n == 2)
		return 1;
	int counter = 0;
	
	for(int n1 = n - 1; n1 * 2 >= n; n1--)
	{
		int n2 = n - 1;
		cout << "n1 is " << n1 << endl;
		cout << "n2 is " << n2 << endl;
		counter++;
		cout << "counter is " << counter << endl;
		if(n2 >= min)
			counter += count_no_permutations(n1, n2);
	}

	
	return counter;
}




n = 3 and 4 work. But n = 5 and on are a little off. This is without permutations, thus 3 + 1 and 1 + 3 are not two, but only counted once, the former (or latter) not being counted.
Any ideas?
Was This Post Helpful? 0
  • +
  • -

#6 militiaman  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 31
  • Joined: 28-August 09

Re: Counting to n, how many different summations

Posted 28 August 2009 - 06:42 PM

Hey Locke, I'm in your class too... in fact, after looking at your picture I believe I have sat next to you almost every day. I'll say hi next class.
This assignment sucks though! I spent 5 hours going over the theory and then my code did absolutely nothing.
Was This Post Helpful? 0
  • +
  • -

#7 jheld  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 04-May 09

Re: Counting to n, how many different summations

Posted 28 August 2009 - 06:58 PM

hey! that's awesome (kinda) that the three of us came here. if you want to try out my permutations function, go for it. it works fine.
Was This Post Helpful? 0
  • +
  • -

#8 militiaman  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 31
  • Joined: 28-August 09

Re: Counting to n, how many different summations

Posted 28 August 2009 - 08:28 PM

View Postjheld, on 28 Aug, 2009 - 05:58 PM, said:

hey! that's awesome (kinda) that the three of us came here. if you want to try out my permutations function, go for it. it works fine.


I just got a permutation function working, and it's strange how different our code is. Yours definitely works too though. Programming always boggles me with how many different solutions can be made.

jheld, what lab session are you in?

My name's Trevor, I'm in Friday 9:00 am.
Was This Post Helpful? 0
  • +
  • -

#9 jheld  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 04-May 09

Re: Counting to n, how many different summations

Posted 28 August 2009 - 08:34 PM

Cool. Yeah, all of the ways you can implement programming algorithms is actually one of the reasons why I love doing it.
I'm in lab Tuesday morning 11-12:50. My name's Jason. Were you in Vector this summer and in 168 with me last semester? I think we had two Trevors in 168 with Chen then.

This post has been edited by jheld: 28 August 2009 - 08:41 PM

Was This Post Helpful? 0
  • +
  • -

#10 Guest_Neumann*


Reputation:

Re: Counting to n, how many different summations

Posted 28 August 2009 - 09:02 PM

You guys still struggle with the non-permutation algorithm?
Was This Post Helpful? 0

#11 jheld  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 04-May 09

Re: Counting to n, how many different summations

Posted 28 August 2009 - 09:03 PM

Correct. My last post with source code shows what I have so far, but it still is a little off. I am pretty sure that it is because of my for-loop's structure, but I am unsure of how to fix that.
Was This Post Helpful? 0
  • +
  • -

#12 militiaman  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 31
  • Joined: 28-August 09

Re: Counting to n, how many different summations

Posted 28 August 2009 - 09:05 PM

Oh hey Jason, yea I was in both of those classes with you. You probably know who I am now.

My non permutation one successfully calculates n=4, 5 and 6 but it fails elsewhere hahaha

BTW here's my "with permutations" code. Mathematically, that's called a composition:

int compositionCount(int n) //includes permutations
{

	//cout << "DEBUG: Stepped into compositionCount("<<n<<")\n";
	int count=0;

	if (n==2)
	{
		//cout << "DEBUG: n="<<n<<", is equal to 2. Return 1\n";
		return 1;
	}
	else
	{
		int k=1;
		//cout << "DEBUG: n="<<n<<", is greater than 2. Run count loop\n";
		while (k < n)
		{
		//cout << "DEBUG: n="<<n<<", k="<<k<<", count="<<count<<endl;
		count += compositionCount(n-k);
		k++;
		}
		count += (n-1);
	}
	return count;
}




Jason, you may find it beneficial to look up "number partitions"

Partition is the mathematical term for the "without permutations" sums.

wikipedia has a page with good information about it to help you understand the math behind it.

This post has been edited by militiaman: 28 August 2009 - 09:09 PM

Was This Post Helpful? 0
  • +
  • -

#13 Guest_Neumann*


Reputation:

Re: Counting to n, how many different summations

Posted 28 August 2009 - 09:12 PM

Ok. Here is the key thing you should note in non-permutation partitions - the numbers are go in the non-decreasing order (of course, there is an opposite way to do these partitions in which numbers go in non-increasing order). For example, here are partitions of 4:

(1 1 1 1), (1 1 2), (1 3), (2 2)

Notice how each successive number is either greater or equal to the number that precedes it.

Locke has made the same topic as you guys. I've posted the code for partitions with permutations, so you might wanna check it out, it's very simple. Here's the topic - http://www.dreaminco...h...=122339&hl=

The code that I've posted there can be easily modified to create a non-permutation partition. Basically, you need to include a third parameter - the first member of the partition. You will use that member to make sure that the successive numbers are either greater or equal to that number. That's all it takes,

This post has been edited by Neumann: 28 August 2009 - 09:16 PM

Was This Post Helpful? 0

#14 militiaman  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 31
  • Joined: 28-August 09

Re: Counting to n, how many different summations

Posted 28 August 2009 - 09:17 PM

View PostNeumann, on 28 Aug, 2009 - 08:12 PM, said:

...


Thanks, I'll check into it.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1