我如何可以生成一个与QUOT;社会高尔夫"矩阵工人的座位安排？ [英] How can I generate a "Social Golfer" matrix for worker seating arrangement?
问题描述
这挑战是一个社会问题高尔夫球场景。我有一个320人的公司。我最近实施了管理通过每一个劳动者，分配目标将按月完成目标（MBO）计划。其中一个反复出现的目标是在工作时间抵达参加30分钟的咖啡和漩每天早晨见面。这次会议，其中有50桌我们的食堂举行。每个表最多可容纳8人最高。加上或减去80个座位是空的每个工作日，因为有目前400我要生成一个循环赛座位安排让每个人都能满足，并与每一个其他人轮流合作一个最大容量。
This challenge is a Social Golfer Problem scenario. I have a company with 320 persons. I recently implemented a Management By Objectives (MBO) program where each worker is assigned goals to be completed on a monthly basis. One of the recurring goals is to arrive on time at work to attend a 30 minute coffee and dounut meeting each morning. The meeting is held in our dinning hall which has 50 tables. Each table can seat up to 8 persons maximum. Plus or minus 80 seats are empty each workday, as there's currently a max capacity for 400. I want to generate a round robin seating arrangement so that each person can meet and collaborate with every other person on a rotating basis.
（编辑）规则：需要8个人的独特设置每个工作日。 。一个人不能与他们在过去坐着，直到所有可能的排列已经用尽其他人再次坐在
(EDIT) RULE: Unique sets of 8 people are required for each workday. A person cannot be seated again with other persons they have sat with in the past until all possible permutations have been exhausted.
编辑：的例子的期望的结果是：
An example of the desired result is:
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工人的每一组（阵列），直到所有重复可能唯一集（排列）已经用尽。接着周期开始从头再来，或许移动的元素，只有到那时，一个工人将与他们以前见过另一名工人就位。那么我想电子邮件作为什么表交给自己坐在下一工作日每个工人。每个工人不知道还有谁在其指定的表sittibg，直到他们在餐桌上到达。只有我将有座位安排完整的阵容。 （这有点音乐椅的游戏）
None of the worker numbers (elements) can repeat in each set (array) of 8 workers until all possible unique sets (permutations) have been exhausted. Then the cycle starts all over again, perhaps shifting the elements, only then, a worker would be seated with another worker they've met before. I would then want to email each worker as to what table they've been assigned to sit at the next work day. Each worker will not know who else is sittibg at their assigned table until they arrive at the table. Only I will have the complete roster for the seating arrangements. (It's sort of a "Musical Chairs" game)
这是不是一个excersise或学校分配。谁使用APL编程语言的一个朋友告诉我，她可以生成一行代码所期望的结果，但我们只使用基于SQL的数据库管理系统（IBM的Informix 11.70和Oracle 11）。
This is not an excersise or school assignment. A friend who uses the APL programming language told me she could generate the desired results with one line of code, but we only use SQL-based DBMS' (IBM Informix 11.70 and Oracle 11).
所以，我有一个SQL表具有以下的列：
So I have an SQL table with the following columns:
employee.id INT {unique primary key}
employee.FullName VARCHAR
...
APL编程下面一行代码生成矩阵排列：
The following one line of APL programming code generates matrix permutations:
pmat2←{{,[⍳2]↑(⊂⊂⎕io,1+⍵)⌷¨⍒¨↓∘.=⍨⍳1+1↓⍴⍵}⍣⍵⍉⍪⍬}
在SQL中，我可以生成一个SELECT语句所期望的结果，我需要多个SELECT INTO TEMP语句，或者需要一个存储过程来获得理想的效果？
In SQL, can I generate the desired results with one SELECT statement, do I need multiple SELECT INTO TEMP statements, or is a stored procedure required to obtain the desired results?
什么都要我的SELECT语句/ s或SP样子？
What should my SELECT statement/s or SP look like?
修改
推荐答案
的？问题结果
。如果问题是一个真正的任务来安排会议再就是在一个提问。结果$ b $一些错误b检查是因为工人的数量，甚至一些可用桌椅不是根本的物理常数：
The problem
If the problem is a real task to schedule meetings then there are some mistakes in posing a question.
It's because number of workers and even a number of available tables and seats not a fundamental physical constant:
- 有人可能被解雇，不能参加下一次会议;
- 人力资源雇佣了10个工人的新项目和所有的人都必须参加下一次会议;
- 在下周开始饭厅装修，只有20桌将可下个月
所以像问题听起来：我们需要安排在未来5-10个工作日的会议在这样的的方式，尽可能多的人，与人，他们以前没有说话，尽可能满足低者作为与其他人的两倍多。
So problem sounds like this: "We need to schedule meetings for next 5-10 working days in a such a way that as many persons as possible meet with persons that they didn't talk before and as low persons as possible talk with another persons twice and more".
因此，问题可能谈是不是产生了全套排列。问题是关于接下来N个会议优化规划。
Therefore the problem isn't about generating a full set of permutations. Problem is about optimal planning for next N meetings.
论结果
问题可以划分为通用的数学优化问题。对于这类问题，我们有一个目标，找到表现为设定参数值（个），功能（S），其目标函数（S）为最大值或最小值的最优解。结果
。要制定问题，我们一定要找到问题的根源：
Theory
Problem can be classified as generic mathematical optimization problem. For that class of problems we have a goal to find optimal solution presented as set of argument value(s) for function(s) which provides maximum or minimum value for objective function(s).
To formulate a problem we must to find the root of the question:
- 每个人最大限度地发挥了一些人，以满足
- 每对人减少一些会议
每个的大约一个对的人之间的对话目标会谈因此，我们必须以相遇。结果
为 P换算制定问题为1的人数，以及我在[ ..P] 和的J [1..P] 作为人指数。结果
为 M 作为会议的数量和米[1 .. M] ，会议数量。结果
那么下面我们来介绍 A（I，J，M）| I< J，I在[1..P]，J在[1..P]，米[1..M] 作为具体会议两个人之间会议的事实。
之后，它可能制订该问题的目标函数和边界条件。
Each of that goals talks about conversations between one pair of persons so we must formulate a problem in terms of "meet".
Denote P as number of persons and i in [1..P] and j in [1..P] as person indexes.
Denote M as quantity of meetings and m in [1 .. M] as meeting number.
Then let's introduce a(i,j,m) | i < j, i in [1..P], j in [1..P], m in [1..M] as a fact of meeting between two persons on concrete meeting.
After that it's possible to formulate an objective function and bounding conditions for the problem.
数学方法结果
请注意，精确解（任何人都满足另一个人只有一次，直到完成周期）可能只有在非常罕见的情况。结果
这是NP完全问题类和最佳匹配的提法是的优化问题在K-统一超图满足1度合作度条件完美匹配。结果
为进一步的理论研究你可以问在的数学或检查的的最新作品可对于k -uniform超图划分，如多项式时间密集超图完美匹配
Math approach
Please note, that the exact solution (anyone meet another person only one time until cycle finished) possible only in very rare cases.
This is NP-complete class problem and best matched formulation is "optimization problem of perfect matching in k-uniform hypergraphs satisfying a 1-degree co-degree condition".
For further theory research you can ask a question at Mathematics or examine latest works available for k-uniform hypergraph partitioning, e.g. "Polynomial-time perfect matchings in dense hypergraphs"
解决方案必须具有完全相同（p-1）/（T-1）=（320-1）/（8-1）= 45.5714285714 的会议，因为每一次人符合其他7和其他号是319.所以可以根据问题的条件了45次会议之前，一些对人召开两次会议。
Solution must have exactly (P-1)/(T-1)=(320-1)/(8-1)=45.5714285714 meetings because every time person meets 7 others and "others" number is 319. So it can be 45 meetings according conditions of the question before some pair of persons meets twice.
有一个类似的具有很好的答案已经在计算器（链接问题）。请注意，这个算法离开空的地方，因为它要求席位选为总理。结果 41的全部安置是使用此解决方案（ SQLFiddle ）查询。
以下的人*黄金= person_count
There are a similar question with good answer already on StackOverflow (link). Note that this algorithm leaves empty places, because for full placement of all persons it requires to seats * prime = person_count and 41 chosen as prime.
Below is query using this solution (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, p.k * p.p), p.k ) x,
trunc( mod(person_id, p.k * p.p) / p.k ) 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, p.p)
) 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
实用方法结果
从实际的角度来看，我们不需要用理论证明正是最佳的解决方案。如果一个人满足另一不止一次这不是什么大不了的事，因此有可能停止在接近最优的解决方案。结果
这样可以对经验规则的基础上产生一个解决方案，如果我们开始通过放置人士其中一个会议和桌试图保持相交的数目为每对尽可能低的人的。结果，
有放置的许多策略可能与其中的一个，如下所示。
Practical approach
From practical point of view we don't need exactly optimal solution with theoretical proof. If one person meet another more than once it's not a big deal, so it's possible to stop at nearly optimal solution.
Such a solution can be generated on basis of empirical rules if we start to place persons one by one to meetings and tables trying to keep number of intersection for each pair of persons as low as possible.
There are many strategies of placing possible and one of them illustrated below.
有关我使用Oracle，因为目前这个问题的标签数据库，它可以在演示 SQLFiddle 网站。
For demonstration purposes I use Oracle because this database present in question tags and it's available at SQLFiddle site.
示例数据库架构设置包括三个表：
Example database schema setup includes three tables:
人 - 表的工人名单;
person - table with list of workers;
person_pair - 表的所有唯一对工人的名单及相交数对于每一对，完全楼（（P * P）/ 2） - 地板（P / 2）行。在的P情况下 = 320它拥有51040行。
person_pair - table with list of all unique pairs of workers and count of intersection for each pair, totally floor((P*P)/2) - floor(P/2) rows. In case of P=320 it holds 51040 rows.
会议 - 表针对每个人每次会议放置信息
meeting - table with placement information for each person on each meeting.
在局限于 20 职工和座位 4 由于资源的数量示例代码数量消耗量限值上SQLFiddle网站，并保持数据集，结果观察到。
In example code number of workers limited to 20 and number of seats to 4 because of resource consumption limits on SQLFiddle site and to keep result datasets observable.
下面是方案的设置和填写代码。请看看通过评论了解更多有关表字段
Below is code for scheme setup and fill. Please look through the comments to find out more about table fields.
-- 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.从列表中选择一个接一个在最适当的地点表的人
Strategy consist of 2 parts:
1. Select persons in specific order;
2. Place persons from list one-by-one at most appropriate table.
在选择列表排号的人是企图把谁尽早以前很多次见面的人，并将其放置在单独的表。
Arranging people in selection list is attempt to place persons who meet before many times before as early as possible and place it at separate tables.
配售者更棘手，主要目的是在那个阶段是最大限度地第一次会议的次数和避免重复会议的数量。所以它靠近施工优化问题合适的目标函数的问题，什么是不平凡的大多数的真实世界的情况下
Placing persons are more tricky and main purpose at that stage is to maximize number of first meetings and minimize number of repeated meetings. So it's close to problem of construction of proper objective function for optimization problem, what is non-trivial in most of a real world cases.
我选择了这个标准：
有关每个表计两个因素：有吸引力（ A ） - 为什么地方人在该表和驱蚊 （研究） - 为什么人不能容纳在该表结果
这个因素toghether组成拿到决赛桌安排的因素：结果$ b。 $ b A * A - （如果A = 0，则0，否则，R / 2）+ R 结果
有吸引力的因素算作人数已经放置在表与当前人之前没有满足。结果
驱蚊的因素算作与表已经全部人员目前人的会议数量的总和。
For each table counted two factors: "attractive"(A) - why place person at that table and "repellent"(R) - why person can't seat on that table.
This factor composed toghether to get final table arranging factor:
-A*A - (if A=0 then 0 else R/2) + R
"Attractive" factor counted as number of persons already placed at the table with which current person not meet before.
"Repellent" factor counted as sum of number of meetings of current person with all persons already at the table.
很有可能它没有那么好，因为它可以，但足以让例子的目的。
为例公式可以扩展到考虑多少时间自上次会议以来已经过去了。
Very probably it not so good as it can, but enough for purposes of example. For example formula can be extended to take into account how much time has been passed since the last meeting.
您可以通过建立良好的表达选购台试验你自己的。
You can experiment with building good expression for choosing table on your own.
接下来是一代会议的代码。
Next is code for generation of meetings.
代码（的 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;
多一点点理论
生成的溶液可以用作起始点一些多标准优化方法的，但要使用它，你必须有这个问题的一个很好的正式提法。
Generated solution can be used as start point for some multicriteria optimization methods, but to use it you must have a good formal formulation of the problem.
希望所有的上述帮助您解决问题。
Hope that all stated above helps you to resolve the problem.
这篇关于我如何可以生成一个与QUOT;社会高尔夫"矩阵工人的座位安排？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
