Created
April 2, 2015 16:50
-
-
Save songmw90/74be17313f1f63c89b7b to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #Author: Khoi | |
| #!/usr/bin/env python | |
| # -*- coding: utf-8 -*- | |
| # items.py should be in the same folder | |
| from items import item_color | |
| from collections import OrderedDict | |
| def are_exclusive(keys, items): | |
| sets = [ items[k] for k in keys ] | |
| return not bool(set.intersection(*sets)) | |
| def union(keys, items): | |
| sets = [ items[k] for k in keys ] | |
| return set.union(*sets) | |
| # helper function: greedy inclusive maximum uncovered values | |
| # @param set current | |
| # @param dict items | |
| # @return string | |
| def get_max_uncover_inclusive_item(current, items): | |
| (max_diff, key) = (0, '') | |
| for k in items: | |
| diff = len(items[k].difference(current)) | |
| if max_diff < diff: | |
| max_diff = diff | |
| key = k | |
| return key | |
| # helper function: greedy exclusive maximum uncovered values | |
| # @param set current | |
| # @param dict items | |
| # @return string | |
| def get_max_uncover_exclusive_item(current, items): | |
| (max_diff, key) = (0, '') | |
| for k in items: | |
| if items[k].isdisjoint(current): | |
| diff = len(items[k].difference(current)) | |
| if max_diff < diff: | |
| max_diff = diff | |
| key = k | |
| return key | |
| # first function | |
| # @param dict items | |
| # @return list | |
| def max_cover_inclusive(items): | |
| items = items.copy() | |
| (covered, keys) = (set(), list()) | |
| while True: | |
| key = get_max_uncover_inclusive_item(covered, items) | |
| if not key: return keys | |
| covered = covered.union(items.pop(key)) | |
| keys.append(key) | |
| # second function | |
| # @param dict items | |
| # @return list | |
| def max_cover_exclusive(items): | |
| items = items.copy() | |
| (covered, keys) = (set(), list()) | |
| while True: | |
| key = get_max_uncover_exclusive_item(covered, items) | |
| if not key: return keys | |
| covered = covered.union(items.pop(key)) | |
| keys.append(key) | |
| # third function | |
| # @param int k | |
| # @param dict items | |
| # @return list | |
| def max_cover_k(k, items): | |
| items = items.copy() | |
| (covered, keys) = (set(), list()) | |
| while len(keys) < k: | |
| key = get_max_uncover_inclusive_item(covered, items) | |
| covered = covered.union(items.pop(key)) | |
| keys.append(key) | |
| return keys | |
| # main entry | |
| if __name__ == '__main__': | |
| # test cases | |
| cases = OrderedDict() | |
| cases['max_cover_inclusive'] = [item_color] | |
| cases['max_cover_exclusive'] = [item_color] | |
| cases['max_cover_k'] = [5, item_color] | |
| # test each case | |
| for case in cases: | |
| print 'Current testcase: {}'.format(case) | |
| params = cases[case] | |
| fn = locals()[case] | |
| result = fn(*params) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment