0

I want to set up an algorithm where I have a list of instances of people for e.g:

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

Now, all of these instances have an attribute with one person that they like, for e.g. jim likes pam, and an attribute with a list of two people that they dislike. So, what would be the most efficient way of comparing the attributes of all of the instances in the list, and then making and finding ALL the number of new lists with only those people that have either one person they like in the new group, or one dislike and one like, but NOT two dislikes.

For e.g.

  • michael hates jan and toby, but likes jim

  • toby hates michael and kevin, but likes pam

So, one list could contain [michael, toby, pam, jim] because even though michael and toby hate eachother but they still have one person that they like. Another list could contains toby but not jim, so michael shouldn't be included in the list since there is no one in there that he likes. AND if a list contains both jan and toby, michael won't still be included even if jim is in there since there are two people that he dislikes in the list.

So, I want to find out ALL of potential number of ways we can group ALL of the people in the list. I have tried to do it in the following way, but it takes a long time to process because of the permutation and I get multiple duplicates. I would appreciate a response, and any further questions on this algorithm. Thank you!

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)
eyllanesc
  • 235,170
  • 19
  • 170
  • 241
Brohi
  • 1

1 Answers1

0

Works pretty quick
without the @functools.lru_cache(maxsize=None), it takes 0.15 seconds with the cache its 0.06

I think there is a smarter answer, this is just brute force

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))
trigonom
  • 528
  • 4
  • 9