using System;
using System.Collections.Generic;
using System.Linq;

namespace PartitionTest {
    public static class Partitioning {
        public static IEnumerable<List<List<T>>> GetAllPartitions<T>(T[] elements, int maxlen) {
        	if (maxlen<=0) {
        		yield return new List<List<T>>();
        	}
        	else {
        		T elem = elements[maxlen-1];
        		var shorter=GetAllPartitions(elements,maxlen-1);
        		foreach (var part in shorter) {
        			foreach (var list in part.ToArray()) {
        				list.Add(elem);
        				yield return part;
        				list.RemoveAt(list.Count-1);
        			}
        			var newlist=new List<T>();
        			newlist.Add(elem);
        			part.Add(newlist);
        			yield return part;
        			part.RemoveAt(part.Count-1);
        		}
        	}
        }
        
		public static void Main()
		{
			foreach(var part in Partitioning.GetAllPartitions(new[] { 1, 2, 3, 4 },4)) {
				Console.WriteLine(string.Join(",",part.Select(x => "("+string.Join(",",x)+")")));
			}
		}
	}
}