c# - How to find all partitions of a set -

i have set of distinct values. looking way generate partitions of set, i.e. possible ways of dividing set subsets.

for instance, set {1, 2, 3} has following partitions:

{ {1}, {2}, {3} }, { {1, 2}, {3} }, { {1, 3}, {2} }, { {1}, {2, 3} }, { {1, 2, 3} }. 

as these sets in mathematical sense, order irrelevant. instance, {1, 2}, {3} same {3}, {2, 1} , should not separate result.

a thorough definition of set partitions can found on wikipedia.

i've found straightforward recursive solution.

first, let's solve simpler problem: how find partitions consisting of 2 parts. n-element set, can count int 0 (2^n)-1. creates every n-bit pattern, each bit corresponding 1 input element. if bit 0, place element in first part; if 1, element placed in second part. leaves 1 problem: each partition, we'll duplicate result 2 parts swapped. remedy this, we'll place first element first part. distribute remaining n-1 elements counting 0 (2^(n-1))-1.

now can partition set 2 parts, can write recursive function solves rest of problem. function starts off original set , finds two-part-partitions. each of these partitions, recursively finds ways partition second part 2 parts, yielding three-part partitions. divides last part of each of these partitions generate four-part partitions, , on.

the following implementation in c#. calling

partitioning.getallpartitions(new[] { 1, 2, 3, 4 }) 

yields

{ {1, 2, 3, 4} }, { {1, 3, 4}, {2} }, { {1, 2, 4}, {3} }, { {1, 4}, {2, 3} }, { {1, 4}, {2}, {3} }, { {1, 2, 3}, {4} }, { {1, 3}, {2, 4} }, { {1, 3}, {2}, {4} }, { {1, 2}, {3, 4} }, { {1, 2}, {3}, {4} }, { {1}, {2, 3, 4} }, { {1}, {2, 4}, {3} }, { {1}, {2, 3}, {4} }, { {1}, {2}, {3, 4} }, { {1}, {2}, {3}, {4} }. 

using system; using system.collections.generic; using system.linq;  namespace partitiontest {     public static class partitioning {         public static ienumerable<t[][]> getallpartitions<t>(t[] elements) {             return getallpartitions(new t[][]{}, elements);         }          private static ienumerable<t[][]> getallpartitions<t>(             t[][] fixedparts, t[] suffixelements)         {             // trivial partition consists of fixed parts             // followed suffix elements 1 block             yield return fixedparts.concat(new[] { suffixelements }).toarray();              // two-group-partitions of suffix elements             // , sub-divide them recursively             var suffixpartitions = gettuplepartitions(suffixelements);             foreach (tuple<t[], t[]> suffixpartition in suffixpartitions) {                 var subpartitions = getallpartitions(                     fixedparts.concat(new[] { suffixpartition.item1 }).toarray(),                     suffixpartition.item2);                 foreach (var subpartition in subpartitions) {                     yield return subpartition;                 }             }         }          private static ienumerable<tuple<t[], t[]>> gettuplepartitions<t>(             t[] elements)         {             // no result if less 2 elements             if (elements.length < 2) yield break;              // generate 2-part partitions             (int pattern = 1; pattern < 1 << (elements.length - 1); pattern++) {                 // create 2 result sets ,                 // assign first element first set                 list<t>[] resultsets = {                     new list<t> { elements[0] }, new list<t>() };                 // distribute remaining elements                 (int index = 1; index < elements.length; index++) {                     resultsets[(pattern >> (index - 1)) & 1].add(elements[index]);                 }                  yield return tuple.create(                     resultsets[0].toarray(), resultsets[1].toarray());             }         }     } }