如何为工人座位安排生成“社交高尔夫球手”矩阵？
这一挑战是社交高尔夫球手问题场景。 我有一个有320人的公司。 我最近实施了一个按目标管理（MBO）计划，其中每个工作人员都被分配了每月完成的目标。 其中一个经常性的目标是按时到达工作，每天早上参加30分钟的咖啡和dounut会议。 会议在我们的餐厅举行，共有50张桌子。 每张桌子最多可容纳8人。 每个工作日正负80个座位是空的，因为目前最大容量为400个。我想生成一个循环座位安排，以便每个人可以轮流与其他人会面和协作。
（编辑）规则：每个工作日需要8人独特。 一个人不能再与他们过去坐过的其他人坐在一起，直到所有可能的排列都已用完为止。
编辑：所需结果的一个例子是：
Day 1: Table 1 will seat worker numbers 1,2,3,4,5,6,7,8. Table 2 will seat worker numbers 9.10,11,12,13,14,15,16 ... Table 50 will seat worker numbers 313,314,315,316,317,318,319,320 **NOTE:** (So, the next workday and thereafter, workers 1 through 8 cannot ever be seated with any other workers from that same set until all possible permutations have been exhausted). Day 2: Table 1 will seat worker numbers 1,17,18,19,20,21,22,23 Table 2 will seat worker numbers 2,10,24,25,26,27,28,29 ... Table 50 will seat worker numbers 305,306,307,308,309,310,311,312 Day N: . . ... . 在所有可能的唯一集合（排列）都已用完之前，所有工作者编号（元素）都不能在8个工作程序的每个集合（数组）中重复。 然后循环重新开始，也许是移动元素，只有这样，一个工人才能与他们以前见过的另一个工人坐在一起。 然后，我想通过电子邮件向每个工作人员发送电子邮件，告知他们在下一个工作日分配了哪些表格。 在他们到达桌子之前，每个工人都不知道还有谁在他们指定的桌子上坐着。 只有我会有完整的座位安排名单。 （这是一种“音乐椅”游戏）
这不是一项例外或学校作业。 使用APL编程语言的朋友告诉我，她可以使用一行代码生成所需的结果，但我们只使用基于SQL的DBMS（IBM Informix 11.70和Oracle 11）。
所以我有一个包含以下列的SQL表：
employee.id INT {unique primary key} employee.FullName VARCHAR ...
以下一行APL编程代码生成矩阵排列：
pmat2←{{,[⍳2]↑(⊂⊂⎕io,1+⍵)⌷¨⍒¨↓∘.=⍨⍳1+1↓⍴⍵}⍣⍵⍉⍪⍬}
在SQL中，我是否可以使用一个SELECT语句生成所需的结果，是否需要多个SELECT INTO TEMP语句，或者是获取所需结果所需的存储过程？
我的SELECT语句或SP应该是什么样的？
编辑 ：如果所需的结果不适用于SQL，是否可以使用像c＃这样的3GL来完成？
这被称为“ 社交高尔夫球手问题 ”，虽然它已经用APL完成，而不是单线。 这实际上是一个非常困难的问题，所以我很难想象它可以通过数据库查询来完成。 网上有很多关于这个主题和一些在线计算器的文献。
编辑：
您的APL代码只是创建一个排列矩阵。 例如，如果输入以下内容：
pmat2←{{,[⍳2]↑(⊂⊂⎕io,1+⍵)⌷¨⍒¨↓∘.=⍨⍳1+1↓⍴⍵}⍣⍵⍉⍪⍬} pmat2 3
你得到以下矩阵：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
根据维基百科：
循环赛 （或全部比赛）是一项“每个参赛者轮流与所有其他参赛者会面”的比赛。
根据Markus Triska的主题论文：
社交高尔夫球手问题 （SGP）是一个组合优化问题。 任务是在g组p个球员中安排g×p个高尔夫球手w周，使得没有两个高尔夫球手不止一次在同一组中比赛。
数学上有一个很大的区别。 一场循环赛将涉及两人一组，所以如果你有9名参赛者，则需要在8轮比赛中进行36场比赛。 对于社交高尔夫球手，您可以按三分组进行分组，并且需要在4轮中进行12场比赛：
6 4 8 1 8 3 1 9 6 9 5 8 3 9 7 4 2 9 4 3 5 4 7 1 5 1 2 5 7 6 8 7 2 6 3 2
问题
如果问题是安排会议的真正任务，那么提出问题就会出现一些错误。
这是因为工人的数量，甚至一些可用的桌子和座位都不是基本的物理常数：
- 某人可能被解雇，无法参加下次会议;
- 人力资源部门为新项目雇佣了10名工人，他们都必须参加下次会议;
- 下周开始翻新餐厅，下个月只有20张桌子可供使用。
所以问题听起来像这样：“我们需要安排下一个5-10个工作日的会议，以便尽可能多的人会见他们之前没有说过话的人，尽可能地与其他人交谈。两次以上“。
因此，问题不在于生成一组完整的排列。 问题是关于下一次N次会议的最佳规划。
理论
问题可以归类为通用数学优化问题 。 对于那类问题，我们的目标是找到最优解，该最优解作为函数的参数值集提供，其为目标函数提供最大值或最小值。
要制定问题，我们必须找到问题的根源：
- 每个人最大限度地满足一些人
- 对于每对人来说，最大限度地减少了一些会议
每个目标都谈到了一对人之间的对话，所以我们必须在“见面”方面提出一个问题。
将P表示为i in [1..P]的人数和i in [1..P] j in [1..P]为人员索引。
将M表示为会议数量，将m in [1 .. M]为会议号码。
然后让我们介绍a(i,j,m) | i < j, i in [1..P], j in [1..P], m in [1..M] a(i,j,m) | i < j, i in [1..P], j in [1..P], m in [1..M]作为两人在具体会议上会面的事实。 之后，可以为问题制定目标函数和边界条件。
数学方法
请注意，确切的解决方案（任何人只有一次见到另一个人，直到周期结束）才有可能只在非常罕见的情况下。
这是NP完全类问题，最佳匹配公式是“满足1度共度条件的k均匀超图中完美匹配的优化问题”。
对于进一步的理论研究，你可以在数学上提出一个问题，或者研究可用于k均匀超图分割的最新工作 ，例如“密集超图中的多项式时间完美匹配”
解决方案必须准确(P-1)/(T-1)=(320-1)/(8-1)=45.5714285714会议，因为每次遇到7个人，“其他”号码是319.所以它可以是45在一对人遇到两次之前根据问题的条件举行会议。
在StackOverflow（ 链接 ）上已经有类似的问题和良好的答案。 请注意，此算法会留下空位，因为对于所有人的完全放置，它需要seats * prime = person_count和41选择为prime。
下面是使用此解决方案（ SQLFiddle ）的查询。
with params as ( select 320 n, -- number of persons 8 k, -- number of seats per table 41 p -- least prime which greather or equal n/k from dual ), person_set as ( select level person_id from dual connect by level <= (select n from params) ), person_map as ( select person_id, mod( mod(person_id, pk * pp), pk ) x, trunc( mod(person_id, pk * pp) / pk ) y from person_set, params p ), meetings as ( select (level-1) meeting_no from dual connect by level <= (select least(k*p, (n-1)/(k-1)) from params) ), seats as ( select (level-1) seat_no from dual connect by level <= (select k from params) ), tables as ( select (level-1) table_no from dual connect by level <= (select p from params) ), meeting_plan as ( select --+ ordered use_nl(seats tables) meeting_no, seat_no, table_no, ( select person_id from person_map where x = seat_no and y = mod(meeting_no*seat_no + table_no, pp) ) person_id from meetings, seats, tables, params p ) select meeting_no, table_no, max(case when seat_no = 0 then person_id else null end) seat1, max(case when seat_no = 1 then person_id else null end) seat2, max(case when seat_no = 2 then person_id else null end) seat3, max(case when seat_no = 3 then person_id else null end) seat4, max(case when seat_no = 4 then person_id else null end) seat5, max(case when seat_no = 5 then person_id else null end) seat6, max(case when seat_no = 6 then person_id else null end) seat7, max(case when seat_no = 7 then person_id else null end) seat8 from meeting_plan group by meeting_no, table_no order by meeting_no, table_no
实用的方法
从实际的角度来看，我们不需要具有理论证据的完全最优解。 如果一个人不止一次遇到另一个人并不是什么大问题，那么就有可能停止接近最佳解决方案。
如果我们开始逐个地将人放在会议和桌子上，试图保持每对人的交叉数尽可能低，则可以基于经验规则生成这样的解决方案。
有许多可能的策略，其中一个说明如下。
出于演示目的，我使用Oracle，因为该数据库存在于问号标签中，并且可以在SQLFiddle站点上获得。
示例数据库架构设置包括三个表：
person - 表与工人名单;
person_pair - 具有所有唯一工人对的列表和每对的交集计数的表，总floor((P*P)/2) - floor(P/2)行。 在P = 320的情况下，它保持51040行。
meeting - 每个会议上每个人的展示位置信息表。
由于SQLFiddle站点上的资源消耗限制并且保持结果数据集可观察，因此示例的代码数量限制为20 ，工作人员数量限制为4 。
以下是方案设置和填充的代码。 请查看注释以了解有关表字段的更多信息。
-- List of persons create table person( person_id number not null -- Unique person identifier. ); -- primary key alter table person add constraint pk_person primary key (person_id) using index; -- List of all possible unique person pairs create table person_pair( person1_id number not null, -- 1st person from pair, refers person table. person2_id number not null, -- 2nd person from pair, refers person table. -- person1_id always less than person2_id. meet_count number -- how many times persons in pair meet each other. ); -- primary key alter table person_pair add constraint pk_person_pair primary key (person1_id, person2_id) using index; -- indexes for search alter table person_pair add constraint idx_pair2 unique (person2_id, person1_id) using index; -- Placement information for meetings create table meeting( meeting_number number not null, -- sequential meeting number table_number number not null, -- table number person_id number not null, -- person placed on that table and meeting seat_no number -- seat number ); -- primary key: person can seat on the same table only once in one meeting alter table meeting add constraint pk_meeting primary key (meeting_number, table_number, person_id) using index; -- disallow duplicate seats on the same table during one meeting alter table meeting add constraint miting_unique_seat unique (meeting_number, table_number, seat_no) using index; -- person can participate in meeting only once alter table meeting add constraint miting_unique_person unique (meeting_number, person_id) using index;
填充初始数据（ SQLFiddle ）：
begin -- Fill persons list with initial data insert into person(person_id) select level from dual connect by level <=20; -- generate person pairs insert into person_pair(person1_id, person2_id, meet_count) select p1.person_id, p2.person_id, 0 from person p1, person p2 where p1.person_id < p2.person_id ; end; / select * from person order by person_id / select * from person_pair order by person1_id, person2_id /
生成会议
战略包括两部分：
1.按特定顺序选择人员;
2.将人员列在最合适的桌子上。
在选择列表中安排人员是在尽可能早地将人们聚集在一起之前，并将其放在不同的桌子上。
安置人员更为棘手，在该阶段的主要目的是最大限度地增加首次会议的次数，并尽量减少重复会议的次数。 因此，它接近于为优化问题构造适当目标函数的问题，在大多数现实世界的情况下，这是非平凡的。
我选择这个标准：
对于每张桌子计算两个因素：“有吸引力”（ A ） - 为什么把人放在那张桌子上并且“驱蚊”（ R ） - 为什么人不能坐在那张桌子上。
这个因素组成了得到决赛桌安排因素：
-A*A - (if A=0 then 0 else R/2) + R
“有吸引力的”因素计算为已经摆放在当前人员之前未与之会面的人数。
“驱逐”因子计算为当前人与已经在桌旁的所有人的会议次数之和。
很可能它不是那么好，但足够用于举例的目的。 例如，可以扩展公式以考虑自上次会议以来已经过了多少时间。
您可以尝试构建良好的表达式，以便自己选择表格。
接下来是生成会议的代码。
代码（ SQLFiddle ）
declare vMeetingNumber number; -- number of current meeting vNotMeetPairCount number; -- number of pairs not meet before vTableCapacity number := 4; -- number of places at one table vTableCount number; -- number of tables begin -- get next meeting number for case of continous generation select nvl(max(meeting_number),0) + 1 into vMeetingNumber from meeting; -- count minimum required table number select ceil(count(1)/vTableCapacity) into vTableCount from person; -- number of remaining pairs who don't meet before select count(1) into vNotMeetPairCount from person_pair where meet_count < 1; -- Generate new meetings while not all persons meet each other while (vNotMeetPairCount > 0) loop -- select list of persons to place for cPersons in ( with person_meets as ( select pp.person1_id, pp.person2_id, pp.meet_count, ( row_number() over ( order by pp.meet_count desc, pp.person1_id ) ) row_priority from person_pair pp ) select person_id from ( select person_id, sum(pair_meet_count*pair_meet_count) pair_meetings from ( select person1_id person_id, meet_count pair_meet_count from person_meets union all select person2_id person_id, meet_count pair_meet_count from person_meets ) group by person_id ) order by pair_meetings desc ) loop -- add current person to most applicable table insert into meeting(meeting_number, table_number, person_id, seat_no) select vMeetingNumber, table_number, cPersons.person_id, seat_no from ( with available_tables as ( select table_number, places_occupied from ( select t.table_number, ( select count(1) from meeting m where m.meeting_number = vMeetingNumber and m.table_number = t.table_number ) places_occupied from ( select level table_number from dual connect by level <= vTableCount ) t ) where places_occupied < vTableCapacity ) select table_number, seat_no, ( row_number() over ( order by -attractor_factor*attractor_factor - decode(attractor_factor,0,0,repellent_factor/2) + repellent_factor ) ) row_priority from ( select t.table_number, t.places_occupied + 1 seat_no, ( select count(1) from meeting m, person_pair pp where m.table_number = t.table_number and m.meeting_number = vMeetingNumber and pp.person1_id = least(m.person_id, cPersons.person_id) and pp.person2_id = greatest(m.person_id, cPersons.person_id) and pp.meet_count = 0 ) attractor_factor, ( select nvl(sum(meet_count),0) from meeting m, person_pair pp where m.table_number = t.table_number and m.meeting_number = vMeetingNumber and pp.person1_id = least(m.person_id, cPersons.person_id) and pp.person2_id = greatest(m.person_id, cPersons.person_id) and pp.meet_count > 0 ) repellent_factor, 1 random_factor --trunc(dbms_random.value(0,1000000)) random_factor from available_tables t ) ) where row_priority = 1 ; end loop; -- Update number of meets update person_pair set meet_count = meet_count + 1 where (person1_id, person2_id) in ( select m1.person_id person1_id, m2.person_id person2_id from meeting m1, meeting m2 where m1.meeting_number = vMeetingNumber and m2.meeting_number = vMeetingNumber and m1.table_number = m2.table_number and m1.person_id < m2.person_id ) ; -- advice to next meeting vMeetingNumber := vMeetingNumber + 1; -- count pairs who don't meet before select count(1) into vNotMeetPairCount from person_pair where meet_count < 1; end loop; end;
多一点理论
生成的解决方案可以用作某些多标准优化方法的起点，但要使用它，您必须对问题进行良好的正式表述。
希望以上所述都能帮助您解决问题。
我实际上不知道这是否有效，但是你可以只创建一个表并插入个人表（只有id就足够了）8次交叉连接和where子句，在第二次连接中排除employee.id（第二栏）！= employee.id（第一栏）。 在第三次交叉加入你必须到employee.id（第三栏）！= employee.id（第二栏）…..
在我看来会产生所有组合。 然后你只需要随机选择一个并保存它，所以你不要再选择它。
在SQL中，答案实际上非常简单，它需要2个表，一个表定义员工，另一个表定义表席。 如：
表：员工
列：
EmployeeID – 必须是唯一标识符。 EmployeeName ActiveEmployee – （Y / N）等
表：座位
列：
SeatID – 必须是唯一标识符。 TableNumber TableSeatNumber等
现在定义一个没有连接标准的查询，称为笛卡尔积，通常是一个不合需要的结果，但在这种情况下并不是一些数据仓库实现。
Select EmployeeID, SeatID from Employees, Seating where ActiveEmployee = 'Y' order by TableSeatNumber, TableNumber;
这将为您提供每个座位的每位员工的结果。 该排序首先在不同的表格中为整个人口产生不同的席位。 如果您的员工人数有很多营业额，那么将结果与历史进行比较，然后从笛卡尔积中否定该实例。
如果您想要更多地混合座位，可以使用排序顺序的其他选项，例如唯一字段。
希望这可以帮助。