In [19]:

    

import random

class Matcher(object):

    def __init__(self, users, user_history):
        self.users = users
        self.user_history = user_history
    
    def random_matcher(self):
        """Randomly assign pairs of users.

        Returns a tuple:
            - a list of lists, representing user-pairings
            - a list of unpaired users."""

        user_options = set(self.users)
        matches = []
        while len(user_options) >= 2:
            new_pair = random.sample(user_options, 2)
            matches.append(new_pair)
            user_options = user_options - set(new_pair)
        # print(matches)
        # print('Remainder: {}'.format(list(user_options)))
        return matches, list(user_options)
    
    def find_repeat_pairs(self, matches):
        """Finds pairs that have been previously matched.

        Returns a list of lists (representing user-pairings) that have already been matched"""

        rematched = []

        for match in matches:
            if match[0] in self.user_history[match[1]]:
                rematched.append(match)

        return rematched
    
    def matching_algorithm(self, num_iters=100):
        # Initialize score
        current_score = len(self.users)
        score = current_score

        # Initialize matches
        matches = []
        unmatched = []
        
        i = 0

        for i in range(num_iters):
#             print('\nIteration: {}'.format(i))
            current_matches, current_unmatched = self.random_matcher()

            current_score = len(current_unmatched) + 2 * len(self.find_repeat_pairs(current_matches))
#             print('Current score: {}'.format(current_score))
#             print('Current matched: {}'.format(current_matches))
#             print('Current unmatched: {}'.format(current_unmatched))
            if current_score < score:
#                 print('Beat previous iteration! Updating score...')
                matches = current_matches
                unmatched = current_unmatched
                score = current_score

            if score <= 1:
                break

        # Update history
        for match in matches:
            self.user_history[match[0]].add(match[1])
            self.user_history[match[1]].add(match[0])
            
        print('# of iterations: {}'.format(i+1))

        return matches, unmatched, score


    

In [14]:

    

num_users = 30
users = list(range(num_users))
user_history = {
    u: set([]) for u in users
}
matcher = Matcher(users, user_history)


    

In [15]:

    

matches, unmatched, score = matcher.matching_algorithm()
print('\n\nRESULTS')
print('Score: {}'.format(score))
print('Matches: {}'.format(matches))
print('Unmatched users: {}'.format(unmatched))


    

    




Iteration: 0
Current score: 0
Current matched: [[23, 3], [26, 2], [8, 25], [1, 15], [16, 19], [29, 17], [21, 10], [14, 7], [0, 6], [18, 22], [11, 27], [20, 9], [5, 13], [24, 4], [12, 28]]
Current unmatched: []
Beat previous iteration! Updating score...


RESULTS
Score: 0
Matches: [[23, 3], [26, 2], [8, 25], [1, 15], [16, 19], [29, 17], [21, 10], [14, 7], [0, 6], [18, 22], [11, 27], [20, 9], [5, 13], [24, 4], [12, 28]]
Unmatched users: []

In [26]:

    

num_users = 30
users = list(range(num_users))
user_history = {
    u: set([]) for u in users
}
matcher2 = Matcher(users, user_history)

num_days = 29
for i in range(num_days):
    print('\nDay: {}'.format(i))
    matches, unmatched, score = matcher2.matching_algorithm(num_iters=1000000)
#     print('\n\nRESULTS')
    print('Score: {}'.format(score))
#     print('Matches: {}'.format(matches))
#     print('Unmatched users: {}'.format(unmatched))


    

    




Day: 0
# of iterations: 1
Score: 0

Day: 1
# of iterations: 6
Score: 0

Day: 2
# of iterations: 1
Score: 0

Day: 3
# of iterations: 4
Score: 0

Day: 4
# of iterations: 4
Score: 0

Day: 5
# of iterations: 12
Score: 0

Day: 6
# of iterations: 40
Score: 0

Day: 7
# of iterations: 116
Score: 0

Day: 8
# of iterations: 37
Score: 0

Day: 9
# of iterations: 10
Score: 0

Day: 10
# of iterations: 655
Score: 0

Day: 11
# of iterations: 102
Score: 0

Day: 12
# of iterations: 223
Score: 0

Day: 13
# of iterations: 2098
Score: 0

Day: 14
# of iterations: 9517
Score: 0

Day: 15
# of iterations: 6920
Score: 0

Day: 16
# of iterations: 41720
Score: 0

Day: 17
# of iterations: 88376
Score: 0

Day: 18
# of iterations: 476337
Score: 0

Day: 19
# of iterations: 1000000
Score: 2

Day: 20
# of iterations: 1000000
Score: 2

Day: 21
# of iterations: 1000000
Score: 4

Day: 22
# of iterations: 1000000
Score: 6

Day: 23
# of iterations: 1000000
Score: 6

Day: 24
# of iterations: 1000000
Score: 6

Day: 25
# of iterations: 1000000
Score: 8

Day: 26
# of iterations: 1000000
Score: 10

Day: 27
# of iterations: 1000000
Score: 10

Day: 28
# of iterations: 1000000
Score: 12

In [ ]: