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)+")"))); } } } }
Standard input is empty
(1,2,3,4) (1,2,3),(4) (1,2,4),(3) (1,2),(3,4) (1,2),(3),(4) (1,3,4),(2) (1,3),(2,4) (1,3),(2),(4) (1,4),(2,3) (1),(2,3,4) (1),(2,3),(4) (1,4),(2),(3) (1),(2,4),(3) (1),(2),(3,4) (1),(2),(3),(4)