8000 Merge branch 'set-cover' · rubonz/swift-algorithm-club@03ee825 · GitHub
[go: up one dir, main page]

Skip to content

Commit 03ee825

Browse files
committed
Merge branch ' 8000 set-cover'
2 parents 5c09860 + a573bb2 commit 03ee825

File tree

1 file changed

+16
-2
lines changed

1 file changed

+16
-2
lines changed

Set Cover (Unweighted)/README.markdown

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,25 @@
11
# Set Cover (Unweighted)
22

3-
A cover
3+
If you have a group of sets, this algorithm finds a subset of those sets within that group whose union will cover an initial set that you're trying to match. The initial set is also known as the universe.
44

5-
If you have a set (also called the universe in the mathematical descriptions of the problem)
5+
For example, suppose you have a universe of `{1, 5, 7}` and you want to find the sets which cover the universe within the following group of sets:
6+
7+
> {8, 4, 2}
8+
> {3, 1}
9+
> {7, 6, 5, 4}
10+
> {2}
11+
> {1, 2, 3}
12+
13+
You can see that the sets `{3, 1} {7, 6, 5, 4}` when unioned together will cover the universe of `{1, 5, 7}`. Yes, there may be additional elements in the sets returned by the algorithm, but every element in the universe is represented.
14+
15+
If there is no cover within the group of sets, the function returns nil. For example, if your universe is `{7, 9}`, there is no combination of sets within the grouping above that will yield a cover.
616

717
## The algorithm
818

19+
The Greedy Set Cover algorithm (unweighted) is provided here. It's known as greedy because it uses the largest intersecting set from the group of sets first before examining other sets in the group.
20+
21+
The function (named `cover`) is provided as an extension of the Swift type `Set`. The function takes a single parameter, which is an array of sets. This array represents the group, and the set itself represents the universe.
22+
923
## See also
1024

1125
[Set cover problem on Wikipedia](https://en.wikipedia.org/wiki/Set_cover_problem)

0 commit comments

Comments
 (0)
0