I though this would be straightforward, unfortunately, it is not.
I am trying to build a function to take an iterable of dictionaries (i.e., a list of unique dictionaries) and return a list of lists of unique groupings of the dictionaries.
x players I would like to form k teams of n size.This question and set of answers from CMSDK is the closest thing to a solution I can find. In adapting it from processing strings of letters to dictionaries I am finding my Python skills inadequate.
The original function that I am adapting comes from the second answer:
import itertools as it
def unique_group(iterable, k, n):
"""Return an iterator, comprising groups of size `k` with combinations of size `n`."""
# Build separate combinations of `n` characters
groups = ("".join(i) for i in it.combinations(iterable, n)) # 'AB', 'AC', 'AD', ...
# Build unique groups of `k` by keeping the longest sets of characters
return (i for i in it.product(groups, repeat=k)
if len(set("".join(i))) == sum((map(len, i)))) # ('AB', 'CD'), ('AB', 'CE'), ...
My current adaptation (that utterly fails with an error of TypeError: object of type 'generator' has no len() because of the call to map(len, i)):
def unique_group(iterable, k, n):
groups = []
groups.append((i for i in it.combinations(iterable, n)))
return ( i for i in it.product(groups, repeat=k) if len(set(i)) == sum((map(len, i))) )
For a bit of context: I am trying to programmatically divide a group of players into teams for Christmas Trivia based on their skills. The list of dictionaries is formed from a yaml file that looks like
- name: Patricia
skill: 4
- name: Christopher
skill: 6
- name: Nicholas
skill: 7
- name: Bianca
skill: 4
Which, after yaml.load produces a list of dictionaries:
players = [{'name':'Patricia', 'skill':4},{'name':'Christopher','skill':6},
{'name':'Nicholas','skill':7},{'name':'Bianca','skill':4}]
So I expect output that would look like a list of these (where k = 2 and n = 2) :
(
# Team assignment grouping 1
(
# Team 1
( {'name': 'Patricia', 'skill': 4}, {'name': 'Christopher', 'skill': 6} ),
# Team 2
( {'name': 'Nicholas', 'skill': 7}, {'name': 'Bianca', 'skill': 4} )
),
# Team assignment grouping 2
(
# Team 1
( {'name': 'Patricia', 'skill': 4}, {'name': 'Bianca', 'skill': 4} ),
# Team 2
( {'name': 'Nicholas', 'skill': 7}, {'name': 'Christopher', 'skill': 6} )
),
...,
# More unique lists
)
Each team assignment grouping needs to have unique players across teams (i.e., there cannot be the same player on multiple teams in a team assignment grouping), and each team assignment grouping needs to be unique.
Once I have the list of team assignment combinations I will sum up the skills in every group, take the difference between the highest skill and lowest skill, and choose the grouping (with variance) with the lowest difference between highest and lowest skills.
I will admit I do not understand this code fully. I understand the first assignment to create a list of all the combinations of the letters in a string, and the return statement to find the product under the condition that the product does not contain the same letter in different groups.
My initial attempt was to simply take the it.product(it.combinations(iterable, n), repeat=k) but this does not achieve uniqueness across groups (i.e., I get the same player on different teams in one grouping).
Thanks in advance, and Merry Christmas!
After a considerable amount of fiddling I have gotten the adaptation to this:
This does not work
def unique_group(iterable, k, n):
groups = []
groups.append((i for i in it.combinations(iterable, n)))
return (i for i in it.product(groups, repeat=k)\
if len(list({v['name']:v for v in it.chain.from_iterable(i)}.values())) ==\
len(list([x for x in it.chain.from_iterable(i)])))
I get a bug
Traceback (most recent call last):
File "./optimize.py", line 65, in <module>
for grouping in unique_group(players, team_size, number_of_teams):
File "./optimize.py", line 32, in <genexpr>
v in it.chain.from_iterable(i)})) == len(list([x for x in
File "./optimize.py", line 32, in <dictcomp>
v in it.chain.from_iterable(i)})) == len(list([x for x in
TypeError: tuple indices must be integers or slices, not str
Which is confusing the crap out of me and makes clear I don't know what my code is doing. In ipython I took this sample output:
assignment = (
({'name': 'Patricia', 'skill': 4}, {'name': 'Bianca', 'skill': 4}),
({'name': 'Patricia', 'skill': 4}, {'name': 'Bianca', 'skill': 4})
)
Which is clearly undesirable and formulated the following test:
len(list({v['name']:v for v in it.chain.from_iterable(assignment)})) == len([v for v in it.chain.from_iterable(assignment)])
Which correctly responds False. But it doesn't work in my method. That is probably because I am cargo cult coding at this point.
I understand what it.chain.from_iterable(i) does (it flattens the tuple of tuples of dictionaries to just a tuple of dictionaries). But it seems that the syntax {v['name']:v for v in ...} does not do what I think it does; either that or I'm unpacking the wrong values! I am trying to test the unique dictionaries against the total dictionaries based on Flatten list of lists and Python - List of unique dictionaries but the answer giving me
>>> L=[
... {'id':1,'name':'john', 'age':34},
... {'id':1,'name':'john', 'age':34},
... {'id':2,'name':'hanna', 'age':30},
... ]
>>> list({v['id']:v for v in L}.values())
Isn't as easy to adapt in this circumstance as I thought, and I'm realizing I don't really know what is getting returned in the it.product(groups, repeat=k). I'll have to investigate more.
A list of dicts is not a good data structure for mapping what you actually want to rearrange, the player names, to their respective attributes, the skill ratings. You should transform the list of dicts to a name-to-skill mapping dict first:
player_skills = {player['name']: player['skill'] for player in players}
# player_skills becomes {'Patricia': 4, 'Christopher': 6, 'Nicholas': 7, 'Blanca': 4}
so that you can recursively deduct a combination of n players from the pool of players iterable, until the number of groups reaches k:
from itertools import combinations
def unique_group(iterable, k, n, groups=0):
if groups == k:
yield []
pool = set(iterable)
for combination in combinations(pool, n):
for rest in unique_group(pool.difference(combination), k, n, groups + 1):
yield [combination, *rest]
With your sample input, list(unique_group(player_skills, 2, 2)) returns:
[[('Blanca', 'Christopher'), ('Nicholas', 'Patricia')],
[('Blanca', 'Nicholas'), ('Christopher', 'Patricia')],
[('Blanca', 'Patricia'), ('Christopher', 'Nicholas')],
[('Christopher', 'Nicholas'), ('Blanca', 'Patricia')],
[('Christopher', 'Patricia'), ('Blanca', 'Nicholas')],
[('Nicholas', 'Patricia'), ('Blanca', 'Christopher')]]
You can get the combination with the lowest variance in total skill ratings by using the min function with a key function that returns the skill difference between the team with the highest total skill ratings and the one with the lowest, which takes only O(n) in time complexity:
def variance(groups):
total_skills = [sum(player_skills[player] for player in group) for group in groups]
return max(total_skills) - min(total_skills)
so that min(unique_group(player_skills, 2, 2), key=variance) returns:
[('Blanca', 'Nicholas'), ('Christopher', 'Patricia')]