首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >根据一定的标准,在组合中从个人中寻找最优组合

问根据一定的标准,在组合中从个人中寻找最优组合
EN

Stack Overflow用户
提问于 2022-05-12 17:15:19
回答 1查看 95关注 0票数 0

我想由一些人组成随机小组。对于个人,我有关于他们的位置(两种可能性)和团队在他们所属的位置的信息。目前还不清楚有多少人会加入。这些小组应在下列限制的基础上成立:

  • 团体一般由3-4人组成。
  • 在一组内,地点之间的份额(2种可能性)应尽可能相等,这意味着在一个由4人组成的小组中,每个地点有2人(2:2),在一个3人组中,每个地点2人,另一人1人(2:1)。
  • 来自同一地点的团队中的人应该属于不同的团队。
  • 再次应用脚本/算法应该会导致组的不同组合,但也是一个同样最优的结果(这个标准不一定是完全填充的)

非常基本的示例

我有8个人。其中4名来自地点x,4名来自地点y,4名来自地点x,2名来自小组1 (x-1),2名来自小组2 (x-2)。来自y (y-1,y-1,y-2,y-2)的4个人也是如此。理想的解决办法是由下列成员组成的两组4人组成:

  • 第一组: x-1,x-2,y-1,y-2
  • 第2组: x-1,x-2,y-1,y-2分组在地点间和来自同一地点的个体中所占份额相同,团队各不相同。

这种情况的最坏解决办法如下:

  • 第1组: x-1,x-1,x-2,x-2
  • 组2: y-1,y-1,y-2,y-2

在一个群体中,所有的人都来自同一个地点。来自同一地点的多个人也属于同一团队。

--我目前正在使用python来解决这个问题,但是我也很乐意使用R。

我基本上建立的小组的数量和规模。其他/ case_when条款。在至少三人的情况下,N为最低人数(个人数/4),R为个人/4除数的剩余/剩余数,情况如下:

  1. R=0->N群,每个群有4个个体
  2. R=1,N<2->1群,5个个体
  3. R=1,N >= 2->3群,3个体,N-3群,4个体
  4. R=2->2群,有3个人,N-1群,4人
  5. R=3->1群,3个个体和4个个体的N群

首先,我正在使用itertools.combinations()计算四/三个个体中的组的所有可能组合。之后,我根据规定的标准对这些组进行评级,并删除那些评级不足的组。

根据我需要的4/3大小的组数,我创建了一个嵌套列表,它由多个可能的3-pax-和4-pax-组组成,目的是使用itertools.product()从x组中找到可能的组合。在接下来的步骤中,我删除了包含同一组的组合,这些组合不止一次。

目前我一直在研究如何删除与个人内部有重叠的组的组合。考虑了定制itertools.product()-method并包含限制,但到目前为止我还没有成功。

而且,这种方法需要大量的资源(运行时),这些资源以个人的数量呈指数增长。因此,任何关于不同、更有效的方法的提示都是非常受欢迎的。

代码语言:javascript
复制
import pandas as pd
import math
import itertools
import collections

# Example dataset
df = pd.DataFrame(data={"ID": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
                        "Name": ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"],
                        "Location": ["y", "x", "y", "x", "x", "x", "y", "x", "x", "y"],
                        "Team": ['1', '1', '1', '2', '3', '2', '2', '1', '3', '2']})


# Defining a class for individuals
class Person:
    def __init__(self, personid, location, team, group):
        self.personid = personid
        self.location = location
        self.team = team
        self.group = group

# Create List of Individuals
individuals = []
for n in df.to_dict('records'):
    individuals.append(Person(personid=n['ID'], location=n['Location'], team=n['Team'], group='n/a'))


# Get permutations of four
combinations = list(itertools.combinations(individuals,4))

# store them in a dictionary
dict_combinations_four = {}
counter = 0

for n in combinations:
    counter += 1
    dict_combinations_four["4_"+str(counter)] = n  # resulting in 4_1, 4_2 ... 4_n as Key for combinations

# calculate points for combinations
dict_comb_four_points = {}

for n in dict_combinations_four.keys():
    list_location = []
    list_team = []
    points = 0
    for i in dict_combinations_four[n]:
        list_location.append(i.location)
        list_team.append(i.location + "_" + i.team)
    # 1. different locations:
    cLocation = list(collections.Counter(list_location).items())
    if len(cLocation) == 2:
        if cLocation[0][1] == cLocation[1][1]: # length has to be two, otherwise there is only one location, count has to be 2 == 2 for equal share;
            points += 3
        elif cLocation[0][1] == 3 or cLocation[1][1] == 3: # for share 3:1 or 1:3
            points += 1
    else:
        points += 0
    # 2. different teams within location
    cTeam = list(collections.Counter(list_team).items())
    if len(cTeam) == 4:# in this case there are four different location / team combinations
        points += 3
    elif len(cTeam) == 3:
        points += 1
    else:
        points += 0

    dict_comb_four_points[n] = points

# remove combinations which reach insufficient points
for i in dict_comb_four_points.keys():
    if dict_comb_four_points[i] <=3:
        dict_combinations_four.pop(i)


# get permutations of three
combinations = list(itertools.combinations(individuals,3))

# store them in a dictionary
dict_combinations_three = {}
counter = 0

for n in combinations:
    counter += 1
    dict_combinations_three["3_" + str(counter)] = n  # resulting in 3_1, 3_2 ... 3_n as Key for combinations


# function to get unique values: https://www.geeksforgeeks.org/python-get-unique-values-list/
def unique(list1):
    # insert the list to the set
    list_set = set(list1)
    # convert the set to the list
    unique_list = (list(list_set))
    return(unique_list)

# calculate points for combinations

dict_comb_three_points = {}

for n in dict_combinations_three.keys():
    list_location = []
    list_team = []
    points = 0
    for i in dict_combinations_three[n]:
        list_location.append(i.location)
        list_team.append(i.location + "_" + i.team)
    # 1. different locations:
    if len(unique(list_location)) >=2:
        points += 3
    # 2. different teams within location
    if len(unique(list_team)) == 4:
        points += 3
    elif len(unique(list_team)) == 3:
        points += 1

    dict_comb_three_points[n] = points

# remove combinations which reach insufficient points
for i in dict_comb_three_points.keys():
    if dict_comb_three_points[i] <= 3:
        dict_combinations_three.pop(i)


# How many groups with what sizes are needed? Define Class for groupings:
class Groupings:
    def __init__(self, participants):
        self.participants = participants
        self.num_pax = len(self.participants)
        num_helper = self.num_pax/4
        fl_num_helper = math.floor(num_helper)
        rest = (num_helper - math.floor(num_helper)) * 4
        self.group_four_pax = fl_num_helper if rest == 0 else fl_num_helper - 2 if rest == 1 and fl_num_helper >= 2 else 0 if rest == 1 and fl_num_helper < 2 else fl_num_helper - 1 if rest == 2 else fl_num_helper
        self.group_three_pax = 0 if rest == 0 else 3 if rest == 1 and fl_num_helper >= 2 else 0 if rest == 0 and fl_num_helper < 2 else 2 if rest == 2 else 1
        self.group_five_pax = 1 if rest == 1 and fl_num_helper < 2 else 0
        self.groupsizes = {"four_pax": self.group_four_pax, "three_pax": self.group_three_pax, "five_pax": self.group_five_pax}

# Assign participants to instance of Class, numbers are contained within instance
mysterygroups = Groupings(individuals)


# Create list with repeated group_lists
list_grouping_bins = []
for i in range(mysterygroups.group_four_pax):
    list_grouping_bins.append(list(dict_combinations_four.keys()))
for i in range(mysterygroups.group_three_pax):
    list_grouping_bins.append(list(dict_combinations_three.keys()))


# Find possible combinations of groups:
comb_groups = itertools.product(*list_grouping_bins)

# Remove combinations which contain the same group more than once
comp_groups_clean = []
comp_groups_unclean = []
for i in comb_groups:
    cI = list(collections.Counter(i).items())
    if len(i) == len(cI):
        comp_groups_clean.append(i)
    else:
        comp_groups_unclean.append(i)
EN

回答 1

Stack Overflow用户

发布于 2022-05-13 17:15:21

这里有一个启发式方法,允许您随机创建许多解决方案,前提是不存在任何潜在的问题。可能带来挑战的潜在问题包括:有1人的地点太多,有太多人的地方,或一个完全由一个团队主导的大地点。

关键思想是最大权重匹配,这可以在花算法中找到。也就是说,如果你拿一个图,你可以给每个边1的权重,它会找到一个匹配的尽可能多的配对。如果你给每个边分配一个1的权重加上一个小的随机因子,你会发现哪一个可能的最大匹配取决于这个小的随机因子。

因此,首先构造一个图,其中两个人是连通的当且仅当他们在同一地点和不同的团队。一个最大的匹配现在给你很多对。当然,尽可能多的配对会导致很多4码的队伍,而3码的人就少了。如果你想调整这一点,你可以在你的图表中添加一些空位,连接到很多人。现在有些人会和空位结对,给你更多的单身汉。

在这个配对阶段之后,你有2组和1组。如果你有一个奇数组,随机分成一对,得到偶数组。

现在你构造了一个新的图。如果两个组位于不同的位置,并且至少有一个是一对,则它们是连接在一起的。现在找一个最大匹配。如果一切顺利的话,现在每个人都会分成3-4组,要么是2-1组,要么是2-2组,每个2组由同一地点不同团队的一对成员组成。

每次你运行它,你都会得到一个解决方案。如果你分配随机权重,它们总是不同的。如果您为以前运行中在一起的人分配了一个配对的惩罚,那么您将得到很多分组,它们将与以前的运行不同。

但这一切的核心是花算法。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/72219721

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档