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

Post a Comment

Popular posts from this blog

OneNote Code Format plugin

-
If you are using OneNote like me to keep your shit together and ever wondered why this does not have a built in code formatting option, then your worry days are over. No one wants to see their code lying around without formatting in plain text form , so make use of this plugin to make things prettier. https://www.makeuseof.com/tag/programmer-onenote-coding-add-on/ 
Read more

Wasted about an hour of my life on something so trivial

-
Image
 Ok guys so i wasted about an hour trying to figure out how to bind to the "disabled" property in a textbox in angular. And after trying for a long time i realized that my code is not working as expected because , you have to use null instead of "false" to control it. Please refer to the stackoverflow answer below. Darn it ! https://stackoverflow.com/questions/42179150/how-to-disable-a-input-in-angular2/43765804
Read more

With Values

-
Image
 Using the clause WITH VALUES when you are adding a new column to an existing table using Microsoft SQL Server is a handy little trick. The use of WITH VALUES is when you want to add a default constraint to an existing table that allows null . Because when you add a default constraints that allows null it will NOT fill the existing rows with a value, this can effect your database logics ( if you have written some code depending on these values ).  Let me demonstrate this with some simple tables. Create a simple table CREATE TABLE Students( id int NOT NULL, name varchar(50) NULL ) Add some sample data insert into Student (id,name) values (1,'Cappadonna'), (2,'UGod') Add a new column to the table , with NOT NULL  clause ALTER TABLE Student ADD age int not null CONSTRAINT age_default DEFAULT 99 Now if you query your table you will see that the existing rows are being populated with your default value. This is because we added the constraint as NOT NULL.    No...
Read more