Сравнение атрибутов экземпляров в списке, а затем добавление в новый список

Question

Я хочу настроить алгоритм, в котором у меня есть список экземпляров людей, например:

worst_office = [jim, michael, pam, toby, oscar, kevin, kelly, ryan, jan]

Теперь все эти экземпляры имеют атрибут с одним человеком, который им нравится, например, для Джима. любит pam и атрибут со списком двух людей, которые им не нравятся. Итак, что было бы наиболее эффективным способом сравнения атрибутов всех экземпляров в списке, а затем создания и поиска ВСЕГО числа новых списков только с теми людьми, у которых либо один человек, который им нравится в новой группе, или одна не нравится, и одна нравится, но НЕ две неприязни.

Например,

• Майкл ненавидит Джана и Тоби, но любит Джима

• Тоби ненавидит Майкла и Кевина, но любит Пэм

Итак, один список может содержать [Майкл, Тоби, Пэм, Джим], потому что, хотя Майкл и Тоби ненавижу друг друга, но у них все еще есть один человек, который им нравится. Другой список может содержать Тоби, но не Джима, поэтому Майкла не следует включать в список, так как там нет никого, кто ему нравится. И если в списке есть и jan, и toby, Майкл все равно не будет включен, даже если в нем присутствует jim, поскольку в списке есть два человека, которых он не любит.

Итак, я хочу выяснить ВСЕ о потенциальное количество способов, которыми мы можем сгруппировать ВСЕХ людей в списке. Я попытался сделать это следующим образом, но из-за перестановки обработка занимает много времени, и я получаю несколько дубликатов. Буду признателен за ответ и любые дальнейшие вопросы по этому алгоритму. Спасибо!

def check(first_list, second_list):
  for each_employee in first_list:
    name = each_employee.get_name()
    is_disliked = False
    is_liked = False
    count = 0

    if second_list:
        for j in second_list:
            if name in j.get_dislikes():
                is_disliked = True
                count += 1
            elif name == j.get_likes():
                is_liked = True

    if (is_disliked and not is_liked) or count > 1:
        if each_employee in second_list:
            second_list.remove(each_employee)
    else:
        if each_employee in second_list:
            pass
        else:
            second_list += [each_employee, ]


def checking(office_list):
    z = [1]
    best_office = []
    check(office_list, best_office)
    check(best_office.copy(), best_office)
    if len(best_office) >= 9:   
    #This is to make sure only lists with more than 9 employees are selected
        for i in best_office:
            print(i.get_name())
        print('-----------------------')


perm_employees = itertools.permutations(worst_office)


for x in perm_employees:
    checking(x)

Answer 1

Работает довольно быстро
без @ functools.lru_cache (maxsize = None), для кеша требуется 0,15 секунды 0,06

Я думаю, что есть более разумный ответ, это просто грубая сила

import functools
import itertools as it
import time

start_time = time.time()

worst_office = ["jim", "michael", "pam", "toby", "oscar", "kevin", "kelly", "ryan", "jan"]

like_dislike_dict = {}
like_dislike_dict[("jim", "toby")] = -1
like_dislike_dict[("jim", "oscar")] = -1
like_dislike_dict[("jim", "michael")] = 1
like_dislike_dict[("michael", "pam")] = 1
like_dislike_dict[("michael", "toby")] = -1
like_dislike_dict[("michael", "oscar")] = -1
like_dislike_dict[("pam", "toby")] = -1
like_dislike_dict[("pam", "oscar")] = -1
like_dislike_dict[("pam", "jim")] = 1
like_dislike_dict[("toby", "jim")] = -1
like_dislike_dict[("toby", "michael")] = -1
like_dislike_dict[("toby", "oscar")] = 1
like_dislike_dict[("oscar", "jim")] = -1
like_dislike_dict[("oscar", "michael")] = -1
like_dislike_dict[("oscar", "kevin")] = 1
like_dislike_dict[("kevin", "ryan")] = -1
like_dislike_dict[("kevin", "jim")] = -1
like_dislike_dict[("kevin", "toby")] = 1
like_dislike_dict[("kelly", "jim")] = -1
like_dislike_dict[("kelly", "michael")] = -1
like_dislike_dict[("kelly", "ryan")] = 1
like_dislike_dict[("ryan", "jim")] = -1
like_dislike_dict[("ryan", "michael")] = -1
like_dislike_dict[("ryan", "jan")] = 1
like_dislike_dict[("jan", "jim")] = -1
like_dislike_dict[("jan", "michael")] = -1
like_dislike_dict[("jan", "kelly")] = 1

def partition(collection):
    # from https://stackoverflow.com/questions/19368375/set-partitions-in-python
    if len(collection) == 1:
        yield [ collection ]
        return
    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller

@functools.lru_cache(maxsize=None)
def valid_list(l):
    for name in l:
        per_set = it.product([name], l)
        per_set = frozenset(per_set)
        if not valid_set(per_set):
            return False
    return True


def valid_set(t):
    sum = 0
    in_dict = False
    for per in t:

        if per in like_dislike_dict:

            in_dict = True
            sum+= like_dislike_dict[per]
    if not in_dict or sum<0:
        return False
    return True


partition_list = list(partition(worst_office))
valids = []
for partition_option in partition_list:
    valid = True
    for part in partition_option:
        if not valid_list(frozenset(part)):
            valid = False
    if valid:
        valids.append(partition_option)

print(valids)
print(list(partition_list[-4]))
print("--- %s seconds ---" % (time.time() - start_time))