How to start create an automatic cyclical matching system

Question

I try to study and create an automatic cyclical matching algorithm. The system's purpose is to match the destinations of several employee who want to move from their current division to other division (there are several reasons to move such as they want to move to their hometown or to look after their family). Unfortunately, the company protocol allow them to move when they can find someone from other division who want to place in their position. In practice, the past case, the employee have to find their partners by posting their destination on Facebook group and switch with two or more people for creating their cyclical rotation themselves like this:

Mr.A work for division X and he want to move to division Y.

Mr.B work for division Y and he want to move to division Z.

Mr.C work for division Z and he want to move to division X.

In use case, one of them (suppose Mr.A) have to contact Mr.B and Mr.C to make a cyclically move to achieve their goals. There are more than 2,000 employee face this problem in my company (my company have around 30k employee).

Thus, anyone please suggests me that how can I study and start to create an AI system or other algorithms that able to help my friend easily complete their purposes.

Ps. I has experience and familiar with python

thanks in advance.

Answer 1

In real life I assume you will be getting your data through a DB query since you talk about thousands of records. But for a small sample let's just put our requests in a list. The idea is, start with one request and see if we have some other people whose target location is the source location of our request, then explore each of those to see if we have some more, until we find a cycle.

Since you want the longest cycle, and probably need other criteria as well, we need to compute all the possibilities. Then another function will select the best choice.

This will find all possible cycles for a given request:

from dataclasses import dataclass

@dataclass
class Request():
    code : int
    who : str
    source : str
    target : str
    days : int

requests = [Request(1,'A','X','Y',3),
            Request(2,'B','Y','Z',5),
            Request(3,'C','Z','X',2),
            Request(4,'D','Y','X',3),
            Request(5,'E','W','Y',3)]

cycles = []

def find_cycles(basereq):
    global cycles
    cycles = []
    find_cycles2(basereq, basereq.target, [basereq.code])
    print(cycles)

def find_cycles2(basereq, pivot, cycle):
    global cycles
    for otherreq in [r for r in requests if r.target == basereq.source and r.code not in cycle]:
        if otherreq.source == pivot:
            cycles.append(cycle + [otherreq.code])
        else:
            find_cycles2(otherreq, pivot, cycle + [otherreq.code])

>>> find_cycles(requests[0])
[[1, 3, 2], [1, 4]]
>>> find_cycles(requests[1])
[[2, 1, 3]]
>>> find_cycles(requests[4])
[]