Introduction

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset. The total number of partitions of an n-element set is the Bell number. For example. Bell number for set of 4 elements is equal 15 and newly created set contains:

[[1] [2] [3] [4]]
[[3 4] [2 1]]
[[3] [4] [2 1]]
[[2 4] [3 1]]
[[2] [4] [3 1]]
[[2 3] [4 1]]
[[2] [3] [4 1]]
[[1] [4] [3 2]]
[[1] [3] [4 2]]
[[1] [2] [4 3]]
[[4] [3 2 1]]
[[3] [4 2 1]]
[[2] [4 3 1]]
[[1] [4 3 2]]
[[4 3 2 1]]

How to calculate?

Calculation is based on recursion which is needed to calculate combinations and new sub sets. Let’s start with combination.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func getPartitions(nArr []int, pNum int) [][]int {
	if pNum == 0 {
		return [][]int{}
	}
	if pNum == 1 {
		resp := make([][]int, len(nArr))
		for i, sp := range nArr {
			resp[i] = []int{sp}
		}
		return resp
	}
	resp := make([][]int, 0)
	for _, nElem := range nArr {
		subArr := subtractSlice(nArr, []int{nElem})
		parts := getPartitions(subArr, pNum-1)
		for _, part := range parts {
			part = append(part, nElem)
			if !unorderedContains(part, resp) {
				resp = append(resp, part)
			}
		}
	}
	return resp
}

This method returns set of all possible combinations. For every element recursively invoke the same method without previous element and partition number minus 1, then for every element from result create combination with previous element. If this combination doesn’t exist then add it to set.

If we have all possible combinations for given set, then let’s create partitions of set.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func connections(nArr []int, pNum int) [][][]int {
	if pNum == 0 || len(nArr) == 0 {
		return [][][]int{{}}
	}
	if pNum == 1 {
		r := make([][]int, 0)
		for _, sp := range nArr {
			r = append(r, []int{sp})
		}
		return [][][]int{r}
	}
	if len(nArr) == 2 {
		return [][][]int{{nArr}, {{nArr[0]}, {nArr[1]}}}
	}
	res := make([][][]int, 0)
	subSets := connections(nArr, pNum-1)
	if len(subSets) > 0 {
		res = append(res, subSets...)
	}
	procSubs := make([][]int, 0)
	for _, part := range getPartitions(nArr, pNum) {
		procSubs = append(procSubs, part)
		nArrSub := subtractSlice(nArr, part)
		sub := connections(nArrSub, pNum)
		for _, subElem := range sub {
			subElem = append(subElem, part)
			if !containsArr(res, subElem) {
				res = append(res, subElem)
			}
		}
	}
	return res
}

That function returns recursively possible connections for given set and its partition number which is from N to 1 where N is maximal size of subset. Then for all possible combinations with given set and partition number counts all possible sub connections and joins them creating uniq subset. Every recurring sub set is filtered out by containsArr function.

In a word of conclusion

This is quite complex algorithm which might be probably tuned up and simplified, so if you see any improvement for that let me know! The first field where I would find improvements is checking if result already contains created sub set. Probably in the future I will back here with new idea but for my current business problem this solution is really sufficient.