我想由一些人组成随机小组。对于个人,我有关于他们的位置(两种可能性)和团队在他们所属的位置的信息。目前还不清楚有多少人会加入。这些小组应在下列限制的基础上成立:
非常基本的示例
我有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人组成:
这种情况的最坏解决办法如下:
在一个群体中,所有的人都来自同一个地点。来自同一地点的多个人也属于同一团队。
--我目前正在使用python来解决这个问题,但是我也很乐意使用R。
我基本上建立的小组的数量和规模。其他/ case_when条款。在至少三人的情况下,N为最低人数(个人数/4),R为个人/4除数的剩余/剩余数,情况如下:
首先,我正在使用itertools.combinations()计算四/三个个体中的组的所有可能组合。之后,我根据规定的标准对这些组进行评级,并删除那些评级不足的组。
根据我需要的4/3大小的组数,我创建了一个嵌套列表,它由多个可能的3-pax-和4-pax-组组成,目的是使用itertools.product()从x组中找到可能的组合。在接下来的步骤中,我删除了包含同一组的组合,这些组合不止一次。
目前我一直在研究如何删除与个人内部有重叠的组的组合。考虑了定制itertools.product()-method并包含限制,但到目前为止我还没有成功。
而且,这种方法需要大量的资源(运行时),这些资源以个人的数量呈指数增长。因此,任何关于不同、更有效的方法的提示都是非常受欢迎的。
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)发布于 2022-05-13 17:15:21
这里有一个启发式方法,允许您随机创建许多解决方案,前提是不存在任何潜在的问题。可能带来挑战的潜在问题包括:有1人的地点太多,有太多人的地方,或一个完全由一个团队主导的大地点。
关键思想是最大权重匹配,这可以在花算法中找到。也就是说,如果你拿一个图,你可以给每个边1的权重,它会找到一个匹配的尽可能多的配对。如果你给每个边分配一个1的权重加上一个小的随机因子,你会发现哪一个可能的最大匹配取决于这个小的随机因子。
因此,首先构造一个图,其中两个人是连通的当且仅当他们在同一地点和不同的团队。一个最大的匹配现在给你很多对。当然,尽可能多的配对会导致很多4码的队伍,而3码的人就少了。如果你想调整这一点,你可以在你的图表中添加一些空位,连接到很多人。现在有些人会和空位结对,给你更多的单身汉。
在这个配对阶段之后,你有2组和1组。如果你有一个奇数组,随机分成一对,得到偶数组。
现在你构造了一个新的图。如果两个组位于不同的位置,并且至少有一个是一对,则它们是连接在一起的。现在找一个最大匹配。如果一切顺利的话,现在每个人都会分成3-4组,要么是2-1组,要么是2-2组,每个2组由同一地点不同团队的一对成员组成。
每次你运行它,你都会得到一个解决方案。如果你分配随机权重,它们总是不同的。如果您为以前运行中在一起的人分配了一个配对的惩罚,那么您将得到很多分组,它们将与以前的运行不同。
但这一切的核心是花算法。
https://stackoverflow.com/questions/72219721
复制相似问题