-4

Alright, so one of my friends challenged me to get this done, but I just can't get very far....

What he asked me to do is to make a program that shows and counts ALL the possible parts of an entered number.

Example for 5:

1+1+1+1+1

2+1+1+1

3+1+1

4+1

5

3+2

2+2+1

I would like the program to be written in either C++ or some pseudocode, I wouldn't mind for either.

Anticipated thanks to you all!

Edit: Not duplicate. I requested a solution in c++; and the other one is in Python. Also, my question asks for ALL possible parts that added return the initial number.

Serge
  • 3,387
  • 3
  • 16
  • 34
Zentrix
  • 13
  • 4
  • 2
    what have you done so far? – PYA Oct 29 '18 at 21:28
  • Well, not much... no code done yet, but i have some number breakdowns; and that's all i have. Some hints, perhaps? And by the way, i have seen the wikipedia page related to this, but my friend will know if I would just copy that. – Zentrix Oct 29 '18 at 21:35
  • absolutely unrelated link – Serge Oct 29 '18 at 21:42
  • also, Serge, thanks for the insight, but I would like you to know that this is what i need, or at least to obtain the same number of possible operations that would return the value of N – Zentrix Oct 29 '18 at 21:47
  • Your question is not clear. Are the "parts" to be shown in decreasing order? If so, why is `2+3` one of your examples? Are the "parts" to be positive integers? If so, why is `5+0` one of your examples? Do you mean just `5`? Why is `0` not in any other line? And so on... Please clarify. Also, show some work of your own, even if just explaining some failed attempts. Did you try a web search on the issue? Did you try [Wikipedia](https://en.wikipedia.org/wiki/Partition_(number_theory))? Did you look at similar questions on this site? – Rory Daulton Oct 29 '18 at 21:48
  • https://stackoverflow.com/questions/14053885/integer-partition-algorithm-and-recursion – Serge Oct 29 '18 at 21:55
  • https://pdfs.semanticscholar.org/9613/c1666b5e48a5035141c8927ade99a9de450e.pdf – Serge Oct 29 '18 at 21:57
  • See above links, I suggest you remove 0. Or clarify do you need 4+1+0 as well or just 5 + 0 – Serge Oct 29 '18 at 21:58
  • The parts were arranged by me in decreasing order so that it would have an order (which i would think should be found in the algorithm's behavior). Yes, the parts have to be positive integers, and i included 5+0 because (we can all agree) has some relevance; at least beside 4+1+0. Any way, the 5+0 isn't a deal breaker, may as well be excluded (just like 4+1+0) – Zentrix Oct 29 '18 at 22:09
  • The Layne link points to a diferent problem more general than what you need – Serge Oct 29 '18 at 22:25
  • You requested "some pseudocode" and Python is close to pseudocode. Can't you figure out the algorithm from the Python code in the linked answer? I have an answer for you but will not show it until you show some effort of your own. – Rory Daulton Oct 30 '18 at 09:46
  • @RoryDaulton the first link by Layne is too far from the problem statements, there are posts that are more relevant. Wikipedia is hard to read, too much of irrelevant details (approximations etc) – Serge Oct 30 '18 at 14:35
  • @LayneBernardo see above – Serge Oct 30 '18 at 14:39

1 Answers1

0

For non zero partitions ( imagine boolean separators in array of 1)

2 ** (n-1)

This list would include both 2 + 3 and 3 + 2.

If you allow 0 then infinite.

Serge
  • 3,387
  • 3
  • 16
  • 34
  • mind explaining the formula, please? – Zentrix Oct 29 '18 at 21:43
  • Not quite what i was looking for, if you will... I was told that an N of 10 would be around roughly 42 (or 48; not very sure). This formula returns 18 Also, an N of 1000 should return over 1.000.000 Yes, i know, a struggle of a problem, right? – Zentrix Oct 29 '18 at 21:51
  • https://pdfs.semanticscholar.org/9613/c1666b5e48a5035141c8927ade99a9de450e.pdf – Serge Oct 29 '18 at 21:57
  • ok then for simple solution use stack exhange link it will give you recursive formula – Serge Oct 29 '18 at 22:14
  • for faster algo read the paper – Serge Oct 29 '18 at 22:15
  • yes, this one (https://stackoverflow.com/questions/14053885/integer-partition-algorithm-and-recursion) returns the !BEST! solutions! Again, please explain to me the use of M in this program, because i was unable to find it (couldn't find the crucial usage of the varable) – Zentrix Oct 29 '18 at 22:28
  • m is the limit on max number to be used. while you dont care of that more general problem it helps to build solution for your case. note the answers to the question explain the recursion in details, try to read them, at the least the accepted one – Serge Oct 29 '18 at 22:36
  • to enlist the partitions https://www.geeksforgeeks.org/generate-unique-partitions-of-an-integer/ – Serge Oct 29 '18 at 22:43
  • did you get what p(n,m) means – Serge Oct 29 '18 at 22:50
  • Yes, I hardly get the recursive programs (i don't really like them), it works, but I didn't understand how it works overall, because i would like to transpose it into a loop. – Zentrix Oct 30 '18 at 07:49
  • If you cannot get recursive version, building the loop based might be too difficult for you. – Serge Oct 30 '18 at 11:40