greedy algorithm for maximum independent set cover

    Covers items with sets from candidate sets. Could be made faster.

    CommandLine:
        python -m utool.util_alg --test-greedy_max_inden_setcover

    Example0:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> candidate_sets_dict = {'a': [5, 3], 'b': [2, 3, 5],
        ...                        'c': [4, 8], 'd': [7, 6, 2, 1]}
        >>> items = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        >>> max_covers = None
        >>> tup = greedy_max_inden_setcover(candidate_sets_dict, items, max_covers)
        >>> (uncovered_items, covered_items_list, accepted_keys) = tup
        >>> result = ut.repr4((uncovered_items, sorted(list(accepted_keys))), nl=False)
        >>> print(result)
        ([0, 9], ['a', 'c', 'd'])

    Example1:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> candidate_sets_dict = {'a': [5, 3], 'b': [2, 3, 5],
        ...                        'c': [4, 8], 'd': [7, 6, 2, 1]}
        >>> items = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        >>> max_covers = 1
        >>> tup = greedy_max_inden_setcover(candidate_sets_dict, items, max_covers)
        >>> (uncovered_items, covered_items_list, accepted_keys) = tup
        >>> result = ut.repr4((uncovered_items, sorted(list(accepted_keys))), nl=False)
        >>> print(result)
        ([0, 3, 4, 5, 8, 9], ['d'])

def greedy_max_inden_setcover(candidate_sets_dict, items, max_covers=None):
    """
    greedy algorithm for maximum independent set cover

    Covers items with sets from candidate sets. Could be made faster.

    CommandLine:
        python -m utool.util_alg --test-greedy_max_inden_setcover

    Example0:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> candidate_sets_dict = {'a': [5, 3], 'b': [2, 3, 5],
        ...                        'c': [4, 8], 'd': [7, 6, 2, 1]}
        >>> items = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        >>> max_covers = None
        >>> tup = greedy_max_inden_setcover(candidate_sets_dict, items, max_covers)
        >>> (uncovered_items, covered_items_list, accepted_keys) = tup
        >>> result = ut.repr4((uncovered_items, sorted(list(accepted_keys))), nl=False)
        >>> print(result)
        ([0, 9], ['a', 'c', 'd'])

    Example1:
        >>> # ENABLE_DOCTEST
        >>> from utool.util_alg import *  # NOQA
        >>> import utool as ut
        >>> candidate_sets_dict = {'a': [5, 3], 'b': [2, 3, 5],
        ...                        'c': [4, 8], 'd': [7, 6, 2, 1]}
        >>> items = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        >>> max_covers = 1
        >>> tup = greedy_max_inden_setcover(candidate_sets_dict, items, max_covers)
        >>> (uncovered_items, covered_items_list, accepted_keys) = tup
        >>> result = ut.repr4((uncovered_items, sorted(list(accepted_keys))), nl=False)
        >>> print(result)
        ([0, 3, 4, 5, 8, 9], ['d'])
    """
    uncovered_set = set(items)
    rejected_keys = set()
    accepted_keys = set()
    covered_items_list = []
    while True:
        # Break if we have enough covers
        if max_covers is not None and len(covered_items_list) >= max_covers:
            break
        maxkey = None
        maxlen = -1
        # Loop over candidates to find the biggested unadded cover set
        for key, candidate_items in six.iteritems(candidate_sets_dict):
            if key in rejected_keys or key in accepted_keys:
                continue
            #print('Checking %r' % (key,))
            lenval = len(candidate_items)
            # len(uncovered_set.intersection(candidate_items)) == lenval:
            if uncovered_set.issuperset(candidate_items):
                if lenval > maxlen:
                    maxkey = key
                    maxlen = lenval
            else:
                rejected_keys.add(key)
        # Add the set to the cover
        if maxkey is None:
            break
        maxval = candidate_sets_dict[maxkey]
        accepted_keys.add(maxkey)
        covered_items_list.append(list(maxval))
        # Add values in this key to the cover
        uncovered_set.difference_update(maxval)
    uncovered_items = list(uncovered_set)
    covertup = uncovered_items, covered_items_list, accepted_keys
    return covertup