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

问题描述 投票：5回答：2

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

我正在尝试构建一个函数来获取可迭代的字典（即，唯一字典列表）并返回字典的唯一分组列表的列表。

如果我有x球员，我想形成k队的n队。

来自CMSDK的This问题和一组答案是我能找到的解决方案最接近的问题。为了使它从处理字母串到词典，我发现我的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)，但这并没有实现跨组的唯一性（即，我在一个组中的不同团队中获得相同的玩家）。

提前谢谢，圣诞快乐！

Update:

经过大量的摆弄后，我得到了适应：

这不起作用

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 list of lists和Python - List of unique dictionaries的完整词典的独特词典，但答案给了我

>>> 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)中返回了什么。我将不得不进行更多调查。

python algorithm dictionary combinations itertools
2个回答
2
投票

dicts列表不是一个很好的数据结构，用于映射您实际想要重新排列的内容，玩家名称，各自的属性，技能等级。您应该首先将dicts列表转换为名称到技能的映射dict：

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')]
3
投票

这是我利用集合利用新数据类的地方。您可以通过在装饰器中设置frozen=True来使数据类可以哈希。首先，你将你的玩家添加到一组以获得独特的玩家。那么你就可以获得n个队伍的所有球员组合。然后你可以创建一组独特的团队。然后创建有效的分组，而没有一个玩家在团队中代表不止一次。最后，您可以计算整个团队中整个团队技能水平的最大差异（再次利用组合）并使用它来对有效分组进行排序。所以这样的事情。

from dataclasses import dataclass
from itertools import combinations
from typing import FrozenSet

import yaml


@dataclass(order=True, frozen=True)
class Player:
    name: str
    skill: int


@dataclass(order=True, frozen=True)
class Team:
    members: FrozenSet[Player]

    def total_skill(self):
        return sum(p.skill for p in self.members)


def is_valid(grouping):
    players = set()
    for team in grouping:
        for player in team.members:
            if player in players:
                return False
            players.add(player)
    return True


def max_team_disparity(grouping):
    return max(
        abs(t1.total_skill() - t2.total_skill())
        for t1, t2 in combinations(grouping, 2)
    )


def best_team_matchups(player_file, k, n):
    with open(player_file) as f:
        players = set(Player(p['name'], p['skill']) for p in yaml.load(f))
    player_combs = combinations(players, n)
    unique_teams = set(Team(frozenset(team)) for team in player_combs)
    valid_groupings = set(g for g in combinations(unique_teams, k) if is_valid(g))
    for g in sorted(valid_groupings, key=max_team_disparity):
        print(g)


best_team_matchups('test.yaml', k=2, n=4)

示例输出：

(
    Team(members=frozenset({
        Player(name='Chr', skill=6),
        Player(name='Christopher', skill=6),
        Player(name='Nicholas', skill=7),
        Player(name='Patricia', skill=4)
    })),
    Team(members=frozenset({
        Player(name='Bia', skill=4),
        Player(name='Bianca', skill=4),
        Player(name='Danny', skill=8),
        Player(name='Nicho', skill=7)
    }))
)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.