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) {
        	var lists = new List<List<T>>();
        	var indexes = new int[elements.Length];
        	lists.Add(new List<T>());
        	lists[0].AddRange(elements);
        	for (;;) {
        		yield return lists;
        		int i,index;
        		for (i=indexes.Length-1;; --i) {
        			if (i<=0)
        				yield break;
        			index = indexes[i];
        			lists[index].RemoveAt(lists[index].Count-1);
        			if (lists[index].Count>0)
        				break;
    				lists.RemoveAt(index);
        		}
        		++index;
        		if (index >= lists.Count)
		        	lists.Add(new List<T>());
		        for (;i<indexes.Length;++i) {
		        	indexes[i]=index;
			        lists[index].Add(elements[i]);
			        index=0;
		        }
        	}
        }
        
		public static void Main()
		{
			foreach(var part in Partitioning.GetAllPartitions(new[] { 1, 2, 3, 4 })) {
				Console.WriteLine(string.Join(",",part.Select(x => "("+string.Join(",",x)+")")));
			}
		}
	}

}