This is a set union.
set([“avocado”, “beets”, “carrots”, “tomato”, “banana”])
>>> fruits & vegetables
This is a set intersection.
set([“tomato”])
>>> fruits – vegetables
This is a set difference.
set([“avocado”, “banana”])
>>> vegetables – fruits
What do you think this will do?
151
The set-covering problem
To recap:
• Sets are like lists, except sets can’t have duplicates.
• You can do some interesting operations on sets, like union,
intersection, and difference.
Back to the code
Let’s get back to the original example.
This is a set intersection:
covered = states_needed & states_for_station
covered
is a set of states that were in both
states_needed
and
states_for_station
. So
covered
is the set of uncovered states
that this station covers! Next you check whether this station
covers more states than the current
best_station
:
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
If so, this station is the new
best_station
. Finally, after the
for
loop is over, you add
best_station
to the final list of stations:
final_stations.add(best_station)
You also need to update
states_needed
. Because this station covers
some states, those states aren’t needed anymore:
states_needed -= states_covered
And you loop until
states_needed
is empty. Here’s the full code for
the loop:
while states_needed:
best_station = None
states_covered = set()
for station, states in stations.items():
covered = states_needed & states
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_needed -= states_covered
final_stations.add(best_station)
|
