In [ ]:

    

# Goal: write a few pairing algorithms and test

# Need:
#     - Dataset
#     - Way of tracking previous pairs
#     - Repeatable system for testing new algorithms

# Assumptions:
#     - No one added or removed


    

In [2]:

    

import random


    

In [ ]:

    

# Algorithm:
#     Assign all active users to buckets of 2 - random_matcher()
#     Check score.
#         If score = 0/1, stop
#         If score < current best score, save results
#     Run x-iterations and choose lowest score
#     After finished, update user_history


    

In [9]:

    

def random_matcher(users):
    """Randomly assign pairs of users.
    
    Returns a tuple:
        - a list of lists, representing user-pairings
        - a list of unpaired users."""
    
    user_options = set(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)


    

    




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

In [20]:

    

def find_repeat_pairs(matches, user_history):
    """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 user_history[match[1]]:
            rematched.append(match)

    return rematched


    

In [29]:

    

def matching_algorithm(users, user_history, num_iters=100):
    # Initialize score
    score = len(users)
    current_score = len(users)

    # Initialize matches
    matches = []
    unmatched = []
    
    for i in range(num_iters):
        print('\nIteration: {}'.format(i))
        current_matches, current_unmatched = random_matcher(users)

        current_score = len(current_unmatched) + 2 * len(find_repeat_pairs(current_matches, user_history))
        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:
        user_history[match[0]].add(match[1])
        user_history[match[1]].add(match[0])
        
    return matches, unmatched, score


    

In [26]:

    

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


    

    




{0: set(), 1: set(), 2: set(), 3: set(), 4: set(), 5: set(), 6: set(), 7: set(), 8: set(), 9: set(), 10: set(), 11: set(), 12: set(), 13: set(), 14: set(), 15: set(), 16: set(), 17: set(), 18: set(), 19: set(), 20: set(), 21: set(), 22: set(), 23: set(), 24: set(), 25: set(), 26: set(), 27: set(), 28: set(), 29: set()}

In [24]:

    

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


    

    




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


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

In [30]:

    

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


    

    






Day: 0

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


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



Day: 1

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


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



Day: 2

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


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



Day: 3

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


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



Day: 4

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


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

In [ ]: