Algorithem

Question

Hello...!

I need to develop an algorithem(like a recursive function).
What I want is...if n=4, then I must print all the possibilities that can be built.
like this.....
ex:- if n=4
then answer should be
4
3 , 1
2 , 2
2 , 1, 1
1 , 1, 1, 1

as you can see all above combinations reprsents 4 when they add up(3+1=4, 2+2=4....).
As I know this is related to integer partioning.I went through some algorithems bt I couldnt overcome with a solution.Can anyone give me a solution to generate above output.?It doesnt matter you cant develop a recursive solution.if it's a recursive then it's better.
this is the site I refered: http://www.site.uottawa.ca/~ivan/F49-int-part.pdf

Alan · Answer

Try this (.NET 2.0 or later) which uses a recursive algorithm to generate the partitions of a given integer passed to the program at the command line : using System; using System.Collections.Generic; class Program { static void Main(string[] args) { if (args.Length != 1) { Console.WriteLine(There must be exactly one integer argument); return; } int n; bool isValid = int.TryParse(args[0] out n); if (!isValid || n { Console.WriteLine(Argument must be an integer >= 1); return; } List > parts = GetPartitionList(n); foreach(List numbers in parts) { Console.Write({); for(int i = 0; i { Console.Write(numbers[i]); if (i } Console.WriteLine(}); } Console.ReadKey(); } static List > GetPartitionList(int n) { if (n >(); return GeneratePartitions(nn); } static List > GeneratePartitions(int n int r) { List > parts = new List >(); if (n == 0) { parts.Add(new List ()); return parts; } for (int i = Math.Min(n r); i > 0; i--) { foreach(List part in GeneratePartitions(n - i i)) { part.Insert(0 i); parts.Add(part); } } return parts; } }