import copy
from itertools import combinations


#def group(userlist, distance_function, min_group_size=3, absolute_max_group_size=5):
    #def get_border_penalty(length):
    #    if length > absolute_max_group_size:
    #        return float('Inf')
    #    elif length < min_group_size:
    #        return float('Inf')
    #    return 1

    # generate distance lookup
    #distance_lookup = dict()
    #for user in userlist:
    #    distance_lookup[user] = dict()
    #for a, b in combinations(userlist, 2):
    #    dist = distance_function(a, b)
    #    distance_lookup[a][b] = dist
    #    distance_lookup[b][a] = dist

    #users = [frozenset({i}) for i in range(len(userlist))]

    #def get_distances(list):
    #    distances = []
    #    for a, b in combinations(list, 2):
    #        distances.append(distance_lookup[userlist[a]][userlist[b]])
    #    return distances

    #def get_distance_between_group(group_a, group_b):
    #    return sum([get_distances_to_group(user, group_b) for user in group_a])

    #def get_distances_to_group(user, group):
    #    distance = 0
    #    for group_user in group:
    #        distance += distance_lookup[userlist[group_user]][userlist[user]]
    #    return distance

    #def h(state):
    #    distances = []
    #    for a, b in combinations(state.groups, 2):
    #        distances.append(get_distance_between_group(a, b))

    #    return sum(distances[:state.steps_to_death])

    #def get_extend_costs(group_one, group_two):
    #    spent = 0
    #    for user in group_two:
    #        spent += get_distances_to_group(user, group_one)
    #        group_one.add(user)
    #    return spent

    #class State():
    #    def __init__(self, steps_to_death):
    #        self.steps_to_death = steps_to_death
    #        self.groups = set()
    #        self.spent = 0
    #        self.cost = 0

    #    def __hash__(self):
    #        return hash(frozenset(self.groups))

    #    def __eq__(self, other):
    #        return self.groups == other.groups

    #    def __repr__(self):
    #        return "groups: {}\n steps: {}, spent: {}, cost: {}".format(
    #            [[elem for elem in group] for group in self.groups], self.steps_to_death, self.spent, self.cost)

    #def create_new_states(state: State, upper_limit):
    #    out_states = []
    #    for a, b in combinations(state.groups, 2):
    #        other_part = copy.deepcopy(state.groups)
    #        other_part.remove(a)
    #        other_part.remove(b)

    #        mutable_a = set(a)
    #        mutable_b = set(b)
    #        extend_costs = get_extend_costs(mutable_a, mutable_b)

    #        other_part.add(frozenset(mutable_a))

    #        new_state = State(state.steps_to_death - 1)
    #        new_state.groups = other_part
    #        new_state.spent = state.spent + extend_costs * get_border_penalty(len(mutable_a))
    #        new_state.cost = new_state.spent + h(new_state)

    #        if new_state.cost > upper_limit:
    #            continue
    #        out_states.append(new_state)
    #    return set(out_states)

    #upper_limit = float('Inf')

    #first_state = State(int((len(userlist) / min_group_size) * (min_group_size - 1)))
    #first_state.groups = first_state.groups.union(users)
    #first_state.cost = 0
    #first_state.spent = 0

    # get greedy upper limit
    #greedy_state = copy.deepcopy(first_state)
    #while greedy_state.steps_to_death > 0:
    #    new_states = create_new_states(greedy_state, float('Inf'))
    #    sorted_states = sorted(new_states, key=lambda x: x.cost)
    #    greedy_state = sorted_states[0]
    #print("finished with score of :{}".format(greedy_state.cost))
    #return [[userlist[user] for user in group] for group in greedy_state.groups]

    # upper_limit = greedy_state.spent
    # seen_states = set()
    # unseen_states = set()
    # unseen_states.add(copy.deepcopy(first_state))
    # greedy_take = 5
    # while True:
    #     unseen_sorted = sorted(unseen_states, key=lambda x: x.cost)
    #     if greedy_take and unseen_sorted:
    #         if greedy_take < len(unseen_sorted):
    #             unseen_sorted = unseen_sorted[:-(len(unseen_sorted) - greedy_take)]
    #
    #     unseen_states = set(unseen_sorted)
    #     print(len(unseen_states))
    #
    #     current_state = unseen_sorted[0]
    #     seen_states.add(current_state)
    #     unseen_states.remove(current_state)
    #
    #     if current_state.steps_to_death <= 0:
    #         return current_state
    #
    #     new_states = create_new_states(current_state, upper_limit)
    #     # print(new_states)
    #     for new_state in new_states:
    #         if new_state.steps_to_death <= 0:
    #             return new_state
    #         if new_state not in seen_states:
    #             unseen_states.add(new_state)


def group(user_list, distance_function, min_group_size=3):
    def group_size(number_of_elements, minimum_group_size):
        group_amount = int(number_of_elements / minimum_group_size)
        max_groups = number_of_elements % minimum_group_size
        minimum_groups = group_amount - max_groups
        return minimum_groups

    def group_rating(elements):
        distances_inside_elements = [distance_function(el[0], el[1]) for el in combinations(elements, 2)]
        return sum(distances_inside_elements) / len(distances_inside_elements)

    def add_best_group(elements, minimum_groups, groups):
        if elements:
            if minimum_groups > 0:
                possible_groupings = combinations(elements, min_group_size)
                minimum_groups -= 1
            else:
                possible_groupings = combinations(elements, min_group_size + 1)
            best_group = (0, None)
            for g in possible_groupings:
                rating = group_rating(g)
                if rating > best_group[0]:
                    best_group = (rating, g)
            groups.append(best_group[1])
            return [ele for ele in elements if ele not in best_group[1]], minimum_groups, groups
        return

    min_groups = group_size(len(user_list), min_group_size)
    groupings = []
    while user_list:
        user_list, min_groups, groupings = add_best_group(user_list, min_groups, groupings)

    return groupings
