字典集的所有组合为K N大小的组

Question

虽然这很简单,但遗憾的是,事实并非如此.

我正在尝试构建一个函数来获取可迭代的字典(即,一个唯一的字典列表)并返回字典的唯一分组列表的列表.

如果我有x球员,我想组建k一支n规模很大的球队.

来自CMSDK的这个问题和一组答案是我能找到的解决方案最接近的问题.为了使它从处理字母串到词典,我发现我的Python技能不足.

我正在改编的原始功能来自第二个答案:

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'), ... 

我当前的改编(完全失败,TypeError: object of type 'generator' has no len()由于调用错误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))) )

对于一些上下文:我正在尝试以编程方式将一组玩家分成基于他们技能的圣诞节琐事.字典列表由yaml文件组成,看起来像

- name: Patricia
  skill: 4
- name: Christopher
  skill: 6
- name: Nicholas
  skill: 7
- name: Bianca
  skill: 4

在yaml.load产生词典列表之后:

players = [{'name':'Patricia', 'skill':4},{'name':'Christopher','skill':6},
           {'name':'Nicholas','skill':7},{'name':'Bianca','skill':4}]

所以我希望输出看起来像这些列表(在哪里k = 2和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

)

每个团队分配组需要在团队中拥有独特的参与者(即,团队分配分组中的多个团队中不能有相同的参与者),并且每个团队分配分组都必须是唯一的.

一旦我获得了团队分配组合的列表,我将总结每组中的技能,取最高技能和最低技能之间的差异,并选择具有最高和最低技能之间最低差异的分组(具有差异).

我承认我完全不理解这段代码.我理解第一个用于创建字符串中所有字母组合的列表的分配,以及在产品在不同组中不包含相同字母的条件下查找产品的return语句.

我最初的尝试是简单地采取it.product(it.combinations(iterable, n), repeat=k)但是这并没有实现跨组的唯一性(即,我在一个组中的不同团队中获得相同的玩家).

提前谢谢,圣诞快乐!

---

更新:

经过大量的摆弄后,我得到了适应:

这不起作用

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)])))

我收到了一个错误

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

这让我感到困惑,并明确表示我不知道我的代码在做什么.在ipython中我采用了这个示例输出:

assignment = (
({'name': 'Patricia', 'skill': 4}, {'name': 'Bianca', 'skill': 4}),
({'name': 'Patricia', 'skill': 4}, {'name': 'Bianca', 'skill': 4})
)

这显然是不可取的,并制定了以下测试:

len(list({v['name']:v for v in it.chain.from_iterable(assignment)})) == len([v for v in it.chain.from_iterable(assignment)])

哪个正确回应False.但它在我的方法中不起作用.那可能是因为我现在正在进行货物编码.

我理解是什么it.chain.from_iterable(i)(它将字典元组的元组扁平化为仅仅是一组字典).但似乎语法{v['name']:v for v in ...}并没有做什么,我觉得它; 无论是那个,还是我正在拆包错误的值!我试图根据Flatten列表和Python列出完整词典的独特词典 - 独特词典列表但答案给了我

>>> 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())

在这种情况下并不像我想象的那样容易适应,而且我意识到我真的不知道回归的是什么it.product(groups, repeat=k).我将不得不进行更多调查.

Answer 1

字典列表并不是一个很好的数据结构，无法将您实际想要重新排列的内容（玩家姓名）映射到他们各自的属性（技能等级）。您应该首先将字典列表转换为名称到技能的映射字典：

player_skills = {player['name']: player['skill'] for player in players}
# player_skills becomes {'Patricia': 4, 'Christopher': 6, 'Nicholas': 7, 'Blanca': 4}

这样就可以n从玩家池中递归地扣除玩家组合iterable，直到组数达到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]

根据您的示例输入，list(unique_group(player_skills, 2, 2))返回：

[[('Blanca', 'Christopher'), ('Nicholas', 'Patricia')],
 [('Blanca', 'Nicholas'), ('Christopher', 'Patricia')],
 [('Blanca', 'Patricia'), ('Christopher', 'Nicholas')],
 [('Christopher', 'Nicholas'), ('Blanca', 'Patricia')],
 [('Christopher', 'Patricia'), ('Blanca', 'Nicholas')],
 [('Nicholas', 'Patricia'), ('Blanca', 'Christopher')]]

您可以通过使用带有关键函数的函数来获得总技能评分方差最小的组合min，该函数返回总技能评分最高的团队与最低总技能评分的团队之间的技能差异，这只需要O (n)时间复杂度：

def variance(groups):
    total_skills = [sum(player_skills[player] for player in group) for group in groups]
    return max(total_skills) - min(total_skills)

这样min(unique_group(player_skills, 2, 2), key=variance)返回：

[('Blanca', 'Nicholas'), ('Christopher', 'Patricia')]