setcover

README

go-setcover

This Golang package calculates the smallest combination of sets that covers all elements in that sets. This is also known as the Set cover problem.

Example:

Consider there are four sets {1, 2, 3}, {2, 4}, {3, 4} and {4, 5}. The smallest possible combination of those sets that still cover all elements is {1, 2, 3}, {4, 5}.

mySets := [][]int{{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}
minimalIndices := setcover.GreedyCoverage(mySets) // equals []int{0, 3}

Exceptions:

It isn't guaranteed that this package returns the smallest combination of sets because of the usage of the greedy algorithm.

Consider there are five sets {1, 2}, {2, 3, 4, 5}, {6, 7, 8, 9, 10, 11, 12, 13}, {1, 3, 5, 7, 9, 11, 13} and {2, 4, 6, 8, 10, 12, 13}. The optimal combination is {1, 3, 5, 7, 11, 13} and {2, 4, 6, 8, 10, 12, 13} but the greedy algorithm produces {6, 7, 8, 9, 10, 11, 12, 13}, {2, 3, 4, 5}, {1, 2}, because it always searches for the sets with the biggest count of uncovered elements, first.

Documentation

Index

• func GreedyCoverage(s [][]int) (result [][]int)
• func GreedyCoverageIndex(s [][]int) (resultIndex []int)

Examples

• GreedyCoverage
• GreedyCoverageIndex

Functions

func GreedyCoverage

func GreedyCoverage(s [][]int) (result [][]int)

Example

gc := func(sets [][]int) {
	res := GreedyCoverage(sets)
	fmt.Print(setsToString(sets, false))
	fmt.Println("Result:", setsToString(res, true))
}
gc([][]int{})
gc([][]int{{0}})
gc([][]int{{0}, {1}})
gc([][]int{{1, 2}, {2, 3, 4, 5}, {6, 7, 8, 9, 10, 11, 12, 13}, {1, 3, 5, 7, 9, 11, 13}, {2, 4, 6, 8, 10, 12, 13}})

Output:

nil
Result: nil
S1: 0
Result: 0
S1: 0
S2: 1
Result: 0 # 1
S1: 1 2
S2: 2 3 4 5
S3: 6 7 8 9 10 11 12 13
S4: 1 3 5 7 9 11 13
S5: 2 4 6 8 10 12 13
Result: 6 7 8 9 10 11 12 13 # 2 3 4 5 # 1 2

func GreedyCoverageIndex

func GreedyCoverageIndex(s [][]int) (resultIndex []int)

GreedyCoverageIndex returns a minimum set of sets that covers the whole universe by using the Greedy Set Coverage Algorithm. The resulting subset will still cover the whole universe but its not guaranteed that it's the smallest subset.

Example

gc := func(sets [][]int) {
	res := GreedyCoverageIndex(sets)
	fmt.Print(setsToString(sets, false))
	fmt.Println("Result:", setToString(res, true))
}
// Basic Examples
gc([][]int{})
gc([][]int{{0}})
gc([][]int{{0, 1}})
gc([][]int{{0}, {0}})
gc([][]int{{0}, {1}})
// Advanced Examples
gc([][]int{{0, 2}, {1, 3}, {2, 3}, {0, 1}})
gc([][]int{{0, 1, 2}, {3, 4, 5}, {0, 1, 2, 3, 4, 5}})
gc([][]int{{0, 1}, {2, 3}, {4, 5}, {6, 7}})
gc([][]int{{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}})
gc([][]int{{1, 2}, {2, 3, 4, 5}, {6, 7, 8, 9, 10, 11, 12, 13}, {1, 3, 5, 7, 9, 11, 13}, {2, 4, 6, 8, 10, 12, 13}})

Output:

nil
Result: nil
S1: 0
Result: S1
S1: 0 1
Result: S1
S1: 0
S2: 0
Result: S1
S1: 0
S2: 1
Result: S1 S2
S1: 0 2
S2: 1 3
S3: 2 3
S4: 0 1
Result: S1 S2
S1: 0 1 2
S2: 3 4 5
S3: 0 1 2 3 4 5
Result: S3
S1: 0 1
S2: 2 3
S3: 4 5
S4: 6 7
Result: S1 S2 S3 S4
S1: 1 2 3
S2: 2 4
S3: 3 4
S4: 4 5
Result: S1 S4
S1: 1 2
S2: 2 3 4 5
S3: 6 7 8 9 10 11 12 13
S4: 1 3 5 7 9 11 13
S5: 2 4 6 8 10 12 13
Result: S3 S2 S1