Number-Partitioning
** COPYRIGHT NOTICE : Though it is not a paper or whatever, but all rights are reserved. **
Number partitioning means to write down all the positive sums equal to that number. I believe it is one of the most challenging tasks (if not the most) to find the algorithm that can do it without reapetition of sums. In 2015 I decided to tacle the problem and this is the way I solved it. In order to do this, I redifined Graph definition itself. In my point of view, a Graph is like a chess board, only that you are becoming different pieces based on the state you were in and the new inputs you get!
As a challenge, try to write down the graph which creates the solutions in its creation process (yes graphs can do that according to my definition).
Sample output for n = 17:
-------------------------- Numbers Pertition -------------------------
-------------------------- By : sajed zarrin pour -------------------------
---------------------------------- 2015 -------------------------------
-------------------------- Mail :samim56b@Gmail.com -------------------------
--------------------------------------------------------------------------------
Number : 17
--------------------------------------------------------------------------------
Technical Viwe On Progress:
--------------------------------------------------------------------------------
Directtion | Value
----------- -------
Root : 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
N : 2+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
N : 3+1+1+1+1+1+1+1+1+1+1+1+1+1+1
N : 4+1+1+1+1+1+1+1+1+1+1+1+1+1
N : 5+1+1+1+1+1+1+1+1+1+1+1+1
N : 6+1+1+1+1+1+1+1+1+1+1+1
N : 7+1+1+1+1+1+1+1+1+1+1
N : 8+1+1+1+1+1+1+1+1+1
N : 9+1+1+1+1+1+1+1+1
N : 10+1+1+1+1+1+1+1
N : 11+1+1+1+1+1+1
N : 12+1+1+1+1+1
N : 13+1+1+1+1
N : 14+1+1+1
N : 15+1+1
N : 16+1
P |
R : 15+2
L |
P |
R : 14+2+1
N : 14+3
P |
L |
P |
R : 13+2+1+1
N : 13+3+1
N : 13+4
P |
P |
R : 13+2+2
L |
L |
P |
R : 12+2+1+1+1
N : 12+3+1+1
N : 12+4+1
N : 12+5
P |
P |
R : 12+3+2
L |
P |
R : 12+2+2+1
L |
L |
P |
R : 11+2+1+1+1+1
N : 11+3+1+1+1
N : 11+4+1+1
N : 11+5+1
N : 11+6
P |
P |
R : 11+4+2
L |
P |
R : 11+3+2+1
N : 11+3+3
P |
L |
P |
R : 11+2+2+1+1
R : 11+2+2+2
L |
L |
L |
P |
R : 10+2+1+1+1+1+1
N : 10+3+1+1+1+1
N : 10+4+1+1+1
N : 10+5+1+1
N : 10+6+1
N : 10+7
P |
P |
R : 10+5+2
L |
P |
R : 10+4+2+1
N : 10+4+3
P |
L |
P |
R : 10+3+2+1+1
N : 10+3+3+1
P |
R : 10+3+2+2
L |
L |
P |
R : 10+2+2+1+1+1
R : 10+2+2+2+1
L |
L |
L |
P |
R : 9+2+1+1+1+1+1+1
N : 9+3+1+1+1+1+1
N : 9+4+1+1+1+1
N : 9+5+1+1+1
N : 9+6+1+1
N : 9+7+1
N : 9+8
P |
P |
R : 9+6+2
L |
P |
R : 9+5+2+1
N : 9+5+3
P |
L |
P |
R : 9+4+2+1+1
N : 9+4+3+1
N : 9+4+4
P |
P |
R : 9+4+2+2
L |
L |
P |
R : 9+3+2+1+1+1
N : 9+3+3+1+1
R : 9+3+3+2
L |
P |
R : 9+3+2+2+1
L |
L |
P |
R : 9+2+2+1+1+1+1
R : 9+2+2+2+1+1
R : 9+2+2+2+2
L |
L |
L |
L |
P |
R : 8+2+1+1+1+1+1+1+1
N : 8+3+1+1+1+1+1+1
N : 8+4+1+1+1+1+1
N : 8+5+1+1+1+1
N : 8+6+1+1+1
N : 8+7+1+1
N : 8+8+1
P |
R : 8+7+2
L |
P |
R : 8+6+2+1
N : 8+6+3
P |
L |
P |
R : 8+5+2+1+1
N : 8+5+3+1
N : 8+5+4
P |
P |
R : 8+5+2+2
L |
L |
P |
R : 8+4+2+1+1+1
N : 8+4+3+1+1
N : 8+4+4+1
P |
R : 8+4+3+2
L |
P |
R : 8+4+2+2+1
L |
L |
P |
R : 8+3+2+1+1+1+1
N : 8+3+3+1+1+1
R : 8+3+3+2+1
N : 8+3+3+3
P |
L |
P |
R : 8+3+2+2+1+1
R : 8+3+2+2+2
L |
L |
L |
P |
R : 8+2+2+1+1+1+1+1
R : 8+2+2+2+1+1+1
R : 8+2+2+2+2+1
L |
L |
L |
L |
P |
R : 7+2+1+1+1+1+1+1+1+1
N : 7+3+1+1+1+1+1+1+1
N : 7+4+1+1+1+1+1+1
N : 7+5+1+1+1+1+1
N : 7+6+1+1+1+1
N : 7+7+1+1+1
R : 7+7+2+1
N : 7+7+3
P |
L |
P |
R : 7+6+2+1+1
N : 7+6+3+1
N : 7+6+4
P |
P |
R : 7+6+2+2
L |
L |
P |
R : 7+5+2+1+1+1
N : 7+5+3+1+1
N : 7+5+4+1
N : 7+5+5
P |
P |
R : 7+5+3+2
L |
P |
R : 7+5+2+2+1
L |
L |
P |
R : 7+4+2+1+1+1+1
N : 7+4+3+1+1+1
N : 7+4+4+1+1
R : 7+4+4+2
L |
P |
R : 7+4+3+2+1
N : 7+4+3+3
P |
L |
P |
R : 7+4+2+2+1+1
R : 7+4+2+2+2
L |
L |
L |
P |
R : 7+3+2+1+1+1+1+1
N : 7+3+3+1+1+1+1
R : 7+3+3+2+1+1
N : 7+3+3+3+1
P |
R : 7+3+3+2+2
L |
L |
P |
R : 7+3+2+2+1+1+1
R : 7+3+2+2+2+1
L |
L |
L |
P |
R : 7+2+2+1+1+1+1+1+1
R : 7+2+2+2+1+1+1+1
R : 7+2+2+2+2+1+1
R : 7+2+2+2+2+2
L |
L |
L |
L |
L |
P |
R : 6+2+1+1+1+1+1+1+1+1+1
N : 6+3+1+1+1+1+1+1+1+1
N : 6+4+1+1+1+1+1+1+1
N : 6+5+1+1+1+1+1+1
N : 6+6+1+1+1+1+1
R : 6+6+2+1+1+1
N : 6+6+3+1+1
N : 6+6+4+1
N : 6+6+5
P |
P |
R : 6+6+3+2
L |
P |
R : 6+6+2+2+1
L |
L |
P |
R : 6+5+2+1+1+1+1
N : 6+5+3+1+1+1
N : 6+5+4+1+1
N : 6+5+5+1
P |
R : 6+5+4+2
L |
P |
R : 6+5+3+2+1
N : 6+5+3+3
P |
L |
P |
R : 6+5+2+2+1+1
R : 6+5+2+2+2
L |
L |
L |
P |
R : 6+4+2+1+1+1+1+1
N : 6+4+3+1+1+1+1
N : 6+4+4+1+1+1
R : 6+4+4+2+1
N : 6+4+4+3
P |
L |
P |
R : 6+4+3+2+1+1
N : 6+4+3+3+1
P |
R : 6+4+3+2+2
L |
L |
P |
R : 6+4+2+2+1+1+1
R : 6+4+2+2+2+1
L |
L |
L |
P |
R : 6+3+2+1+1+1+1+1+1
N : 6+3+3+1+1+1+1+1
R : 6+3+3+2+1+1+1
N : 6+3+3+3+1+1
R : 6+3+3+3+2
L |
P |
R : 6+3+3+2+2+1
L |
L |
P |
R : 6+3+2+2+1+1+1+1
R : 6+3+2+2+2+1+1
R : 6+3+2+2+2+2
L |
L |
L |
L |
P |
R : 6+2+2+1+1+1+1+1+1+1
R : 6+2+2+2+1+1+1+1+1
R : 6+2+2+2+2+1+1+1
R : 6+2+2+2+2+2+1
L |
L |
L |
L |
L |
P |
R : 5+2+1+1+1+1+1+1+1+1+1+1
N : 5+3+1+1+1+1+1+1+1+1+1
N : 5+4+1+1+1+1+1+1+1+1
N : 5+5+1+1+1+1+1+1+1
R : 5+5+2+1+1+1+1+1
N : 5+5+3+1+1+1+1
N : 5+5+4+1+1+1
N : 5+5+5+1+1
R : 5+5+5+2
L |
P |
R : 5+5+4+2+1
N : 5+5+4+3
P |
L |
P |
R : 5+5+3+2+1+1
N : 5+5+3+3+1
P |
R : 5+5+3+2+2
L |
L |
P |
R : 5+5+2+2+1+1+1
R : 5+5+2+2+2+1
L |
L |
L |
P |
R : 5+4+2+1+1+1+1+1+1
N : 5+4+3+1+1+1+1+1
N : 5+4+4+1+1+1+1
R : 5+4+4+2+1+1
N : 5+4+4+3+1
N : 5+4+4+4
P |
P |
R : 5+4+4+2+2
L |
L |
P |
R : 5+4+3+2+1+1+1
N : 5+4+3+3+1+1
R : 5+4+3+3+2
L |
P |
R : 5+4+3+2+2+1
L |
L |
P |
R : 5+4+2+2+1+1+1+1
R : 5+4+2+2+2+1+1
R : 5+4+2+2+2+2
L |
L |
L |
L |
P |
R : 5+3+2+1+1+1+1+1+1+1
N : 5+3+3+1+1+1+1+1+1
R : 5+3+3+2+1+1+1+1
N : 5+3+3+3+1+1+1
R : 5+3+3+3+2+1
N : 5+3+3+3+3
P |
L |
P |
R : 5+3+3+2+2+1+1
R : 5+3+3+2+2+2
L |
L |
L |
P |
R : 5+3+2+2+1+1+1+1+1
R : 5+3+2+2+2+1+1+1
R : 5+3+2+2+2+2+1
L |
L |
L |
L |
P |
R : 5+2+2+1+1+1+1+1+1+1+1
R : 5+2+2+2+1+1+1+1+1+1
R : 5+2+2+2+2+1+1+1+1
R : 5+2+2+2+2+2+1+1
R : 5+2+2+2+2+2+2
L |
L |
L |
L |
L |
L |
P |
R : 4+2+1+1+1+1+1+1+1+1+1+1+1
N : 4+3+1+1+1+1+1+1+1+1+1+1
N : 4+4+1+1+1+1+1+1+1+1+1
R : 4+4+2+1+1+1+1+1+1+1
N : 4+4+3+1+1+1+1+1+1
N : 4+4+4+1+1+1+1+1
R : 4+4+4+2+1+1+1
N : 4+4+4+3+1+1
N : 4+4+4+4+1
P |
R : 4+4+4+3+2
L |
P |
R : 4+4+4+2+2+1
L |
L |
P |
R : 4+4+3+2+1+1+1+1
N : 4+4+3+3+1+1+1
R : 4+4+3+3+2+1
N : 4+4+3+3+3
P |
L |
P |
R : 4+4+3+2+2+1+1
R : 4+4+3+2+2+2
L |
L |
L |
P |
R : 4+4+2+2+1+1+1+1+1
R : 4+4+2+2+2+1+1+1
R : 4+4+2+2+2+2+1
L |
L |
L |
L |
P |
R : 4+3+2+1+1+1+1+1+1+1+1
N : 4+3+3+1+1+1+1+1+1+1
R : 4+3+3+2+1+1+1+1+1
N : 4+3+3+3+1+1+1+1
R : 4+3+3+3+2+1+1
N : 4+3+3+3+3+1
P |
R : 4+3+3+3+2+2
L |
L |
P |
R : 4+3+3+2+2+1+1+1
R : 4+3+3+2+2+2+1
L |
L |
L |
P |
R : 4+3+2+2+1+1+1+1+1+1
R : 4+3+2+2+2+1+1+1+1
R : 4+3+2+2+2+2+1+1
R : 4+3+2+2+2+2+2
L |
L |
L |
L |
L |
P |
R : 4+2+2+1+1+1+1+1+1+1+1+1
R : 4+2+2+2+1+1+1+1+1+1+1
R : 4+2+2+2+2+1+1+1+1+1
R : 4+2+2+2+2+2+1+1+1
R : 4+2+2+2+2+2+2+1
L |
L |
L |
L |
L |
L |
P |
R : 3+2+1+1+1+1+1+1+1+1+1+1+1+1
N : 3+3+1+1+1+1+1+1+1+1+1+1+1
R : 3+3+2+1+1+1+1+1+1+1+1+1
N : 3+3+3+1+1+1+1+1+1+1+1
R : 3+3+3+2+1+1+1+1+1+1
N : 3+3+3+3+1+1+1+1+1
R : 3+3+3+3+2+1+1+1
N : 3+3+3+3+3+1+1
R : 3+3+3+3+3+2
L |
P |
R : 3+3+3+3+2+2+1
L |
L |
P |
R : 3+3+3+2+2+1+1+1+1
R : 3+3+3+2+2+2+1+1
R : 3+3+3+2+2+2+2
L |
L |
L |
L |
P |
R : 3+3+2+2+1+1+1+1+1+1+1
R : 3+3+2+2+2+1+1+1+1+1
R : 3+3+2+2+2+2+1+1+1
R : 3+3+2+2+2+2+2+1
L |
L |
L |
L |
L |
P |
R : 3+2+2+1+1+1+1+1+1+1+1+1+1
R : 3+2+2+2+1+1+1+1+1+1+1+1
R : 3+2+2+2+2+1+1+1+1+1+1
R : 3+2+2+2+2+2+1+1+1+1
R : 3+2+2+2+2+2+2+1+1
R : 3+2+2+2+2+2+2+2
L |
L |
L |
L |
L |
L |
L |
P |
R : 2+2+1+1+1+1+1+1+1+1+1+1+1+1+1
R : 2+2+2+1+1+1+1+1+1+1+1+1+1+1
R : 2+2+2+2+1+1+1+1+1+1+1+1+1
R : 2+2+2+2+2+1+1+1+1+1+1+1
R : 2+2+2+2+2+2+1+1+1+1+1
R : 2+2+2+2+2+2+2+1+1+1
R : 2+2+2+2+2+2+2+2+1
L |
L |
L |
L |
L |
L |
L |
P |