Find optimum teams given calendar availabilities

Question

I'm designing an algorithm that creates optimum teams based on everyone's availabilities (maximizes the amount of shared availability). To this end, I've made a function that takes in a dictionary of availabilities mapping person to an array of their availabilities throughout the week at every 15 minute point (e.g. [True, True, False,...,False]) and desired team size and outputs final teams. Here's my working code:

import numpy as np
from itertools import combinations, chain
import operator
from functools import reduce
from tqdm import tqdm
import operator
def ncr(n, r):
    """N Choose R combination"""
    r = min(r, n-r)
    numer = reduce(operator.mul, range(n, n-r, -1), 1)
    denom = reduce(operator.mul, range(1, r+1), 1)
    return numer // denom  # or / in Python 2

NUM_PEOPLE = 100
TEAM_SIZE = 5
time_slots = 24*4*7

# random availabilities
availabilities = np.random.randint(2, size=(NUM_PEOPLE, time_slots), dtype="bool")
availabilities_dict = {}
for i, availability in enumerate(availabilities):
    availabilities_dict[i] = availability

    
    
def make_teams(availabilities_dict, team_size):
    """
    availabilities_dict form: {player: [0,0,0,...,1], player2: [0,0,0,0,1...,0]}
    """

    
    sums = []
    comb = combinations(availabilities_dict, TEAM_SIZE)
    for i in tqdm(list(comb)): 
        sum_of_array = np.logical_and.reduce((np.array(availabilities[i,:]))).sum()
        sums.append((i, sum_of_array))
    sums.sort(key=operator.itemgetter(1))
    sums.reverse()
    
    
    assigned = []
    teams = []
    i = 0
    while (len(assigned) < NUM_PEOPLE):
        considering = list(sums[i][0])
        none_assigned = True
        for person in considering:
            if person in assigned:
                none_assigned = False
        if none_assigned:
            teams.append((considering, sums[i][1]))
            for person in considering:
                assigned.append(person)
        i += 1
    return teams
teams = make_teams(availabilities_dict, TEAM_SIZE)

Example output consists of a list of tuples (team, total blocks intersecting):

[([15, 18, 42, 70, 94], 36),
 ([14, 30, 63, 80, 97], 36),
 ([1, 12, 40, 64, 88], 36),
 ([22, 48, 62, 72, 87], 34),
 ([25, 29, 35, 53, 85], 32),
 ([26, 31, 49, 60, 78], 31),
 ([13, 44, 79, 93, 96], 29),
 ([32, 59, 67, 71, 82], 28),
 ([24, 39, 41, 50, 91], 28),
 ([9, 28, 55, 92, 95], 28),
 ([5, 8, 11, 19, 86], 28),
 ([4, 33, 56, 76, 83], 27),
 ([2, 10, 16, 17, 69], 27),
 ([21, 43, 73, 75, 81], 24),
 ([7, 20, 57, 89, 99], 24),
 ([23, 36, 37, 58, 66], 22),
 ([52, 61, 65, 68, 84], 20),
 ([3, 27, 34, 47, 74], 18),
 ([6, 38, 51, 54, 77], 16),
 ([0, 45, 46, 90, 98], 9)]

But this took over 10 mins to run on my state of the art computer! Is there a way to still find an optimum team match without running through all of the possible combinations? How can I make it faster? Thank you!

Answer 1

Review

Imports

import operator is being done twice, which is unnecessary.

from itertools import combinations, chain: chain is never used, and can be removed.

N Choose R

As of Python 3.8, the "n choose r" function is built-in and can simply be imported:

from math import comb.

The function is never used, so may be deleted.

Constants

time_slots = 24*4*7

That is ... the number of hours in a 4-week month? No? Perhaps you should name some of those numbers, and use UPPER_CASE to indicate the result is a constant:

SLOTS_PER_HR = 4
HRS_PER_DAY = 24
DAYS_PER_WEEK = 7
TIME_SLOTS = SLOTS_PER_HR * HRS_PER_DAY * DAYS_PER_WEEK

Code Organization

You've got imports, function definition, constants, code, another function definition, more code. Organize your code, please!

• imports
• constants
• function definitions
• code (ideally in a main-guard)

Use blank lines to separate sections. Your first function immediately follows the imports without a blank line, which makes it harder to understand. 3 blank lines before the second function definition seems excessive, and no blank line after the last function makes it harder to see that the code which follows is not part of the function.

Order import ... statements before from ... import ... statements.

Use Function Parameters

def make_teams(availabilities_dict, team_size):

If I call make_teams(availabilities, 10), I'd expect the function to make teams of 10, but it will actually make teams of size TEAM_SIZE (a global constant) instead! The team_size parameter is never used.

Similarly, if I pass in a dictionary of 200 people, it will stop making teams when NUM_PEOPLE is reached. len(availabilities_dict) would be more intuitive.

Use a for loop instead of a manual loop counter

    i = 0
    while len(assigned) < NUM_PEOPLE:
        considering = list(sums[i][0])
        ...
        i += 1

This loop can be changed to something like the following, which has eliminated the i loop variable. We've even moved the test for number of people assigned from every loop to only being done when the list of assigned people changes.

    for considering, team_sum in sums:
        ...
        if none_assigned:
            ...
            if not len(assigned) < NUM_PEOPLE:
                break

Large functions

make_teams() is a large function, 22 lines long, not counting blank lines or docstrings. No comment is in sight. Functions should be decomposed into smaller functions, which do simpler tasks, instead of a single monolithic function doing everything. Smaller functions are easier to understand.

Type Hints

Adding type-hints can go a long way towards improving readability of the code.

Optimizations

NumPy -vs- Bitarray

numpy is a powerful, flexible, and fast library for manipulating vast quantities of data in multidimensional arrays.

Most of the power of numpy is completely unused by this code. The part that is being done by numpy could be replaced with bitarray, a library that is optimized exclusively for dealing with arrays of bits in a fast, efficient, memory conscious way.

I haven't run timed trials of numpy using 1-dimensional bit arrays against the bitarray library, so I'm offering this as something to look into, rather than explicitly stating one is better than the other.

Lists -vs- Sets

You are maintaining a list of all assigned players, and testing that no player in a considering list is in the assigned list. The problem is person in assigned is an \$O(N)\$ operation. If you maintained as set of assigned players, then player in assigned becomes an \$O(1)\$ operation, significantly faster.

Moreover, with sets you can test all the players in considering at once. If assigned.isdisjoint(considering) is true, there is no overlap; no player in considering has been assigned.

Suggested code

from bitarray import bitarray
from bitarray.util import urandom
from itertools import combinations

# Types for type-hints (using Python3.9 style)
Schedules = dict[int, bitarray]
Team = tuple[int]
Teams = list[tuple[Team, int]]

# Constants
SLOTS_PER_HR = 4
HRS_PER_DAY = 24
DAYS_PER_WEEK = 7
TIME_SLOTS = SLOTS_PER_HR * HRS_PER_DAY * DAYS_PER_WEEK


def make_teams(availability: Schedules, team_size: int) -> Teams:
    """
    A good docstring here
    """

    # Inner function for determining the common availability of a team
    def common_availability(team: tuple[int]) -> int:
        avail = bitarray(TIME_SLOTS)
        avail.setall(True)
        for player in team:
            avail &= availability[player]
        return avail.count()

    # team combinations are created and sorted in one step.
    team_combinations = sorted(combinations(availability, team_size),
                               key=common_availability, reverse=True)

    # Collect teams, while maintaining a set of assigned players
    assigned = set()
    teams = []

    for team in team_combinations:
        if assigned.isdisjoint(team):
            # I didn't store availability scores, so recalculate here if really needed.
            teams.append((team, common_availability(team)))
            assigned |= set(team)
        
    return teams           

# Create random schedules
def test_data(num_people: int, time_slots: int) -> Schedules:
    return {i: urandom(time_slots) for i in range(num_people)}


if __name__ == '__main__':
    from time import perf_timer

    for num_people in range(TEAM_SIZE, 101, TEAM_SIZE):
        availability = test_data(num_people, TIME_SLOTS)
        start = perf_counter()
        teams = make_teams(availability, TEAM_SIZE)
        secs = perf_counter() - start
        mins = int(secs / 60)
        secs -= mins * 60
        
        print(f"{num_people:3d} {mins:02d}:{secs:06.3f}")

My 5 year old laptop finds teams of 5 from 100 people in 02:08.887 ... well under the 10 minutes you're experiencing on your "state of the art computer". That isn't a really good, qualitative performance comparison, so you'll have to profile it to see how much of an improvement you see.