Finding Partitions of a number

So recently i got a question from my friend Sameera who had this requirement. 

Given a number N , he wanted to generate all possible combinations of n1,n2 where n1 + n2 = N

For example if i give you 25 , you should output :

1,24
2,23
3,22
4,21
5,20
6,19
7,18
9,16
10,15
11,14
12,13

But he had an additional condition as well , these number pairs should not contain an addition which involves a carry . 

( As a non native English speaker this is the first time i even heard that word :) )

So that means in the above example if i gave you 25 , you should only output:

1,24
2,23
3,22
4,21
5,20
10,15
11,14
12,13


Notice that i have left out 

6,19
7,18
9,16

Because adding them involves transferring 1 digit from one place to another. ( Please excuse my language as i am not a mathematician or well versed in maths so im trying to explain this in layman idiot terms here ).

Ok , so in addition to the above mentioned condition he had another condition ( what a pain in the ass right ). And that is , the number he will be providing are not BASE 10 but BASE 5.

For example , if he inputs 21 that means 2*5 + 1*1 => 11

Ok just before i recap the conditions , after Sameera asked me this question i had a chat with my friend and Maths whiz Namesh who told me that these are called Partitions and Ramanujan had some theory about this , you can read up about it if you are interested through the link that i included.

So now , to recap the conditions :

1. Given a number N , we must find all partitions of N containing only 2 number n1 and n2 such that N = n1 + n2

2.When adding n1 and n2 a carry must NOT occur

3. N is given in Base 5

Now to the solution

So after trying my hand at this for a while , i found this wonderful article on Geeks for Geeks that gave me an algorithm to find the carry which occurs while adding 2 numbers. And after almost no modification it seem to work OK for any base between 2 and 10 including.

Your boi Gaba took the liberty to implement rest of the code , but this only works for bases between 2 and 10 included only.

Also i didn't test it super thoroughly since i have like you know.. A JOB which i need to keep to eat and keep myself alive :P. But i think the code works pretty OK for most scenarios.

If you are interested please feel free to check my code on GitHub.

Follow the readme file and code comments for more details.

So that concludes my little side gig , i had fun doing it and im pretty sure that this is not the best way to achieve my requirement that is why i thought of posting this. If you guys can comeup with better algorithms to get this done , then let's talk ! :) 

Cheers ! 


Comments

Popular posts from this blog

Wasted about an hour of my life on something so trivial

Installing XDebug on Windows + XAMPP + VSCode

Connecting to AWS DynamoDb with .NET CORE