我希望一个活动生成一个满足某些条件的表，例如：
我们尝试在 Excel 中手动生成它，但总是有一些组再次看到对方。
我们试图手动“生成一个列表”，但我们总是结束我们的团队相互交叉，比如在这个例子中团队 7 和团队 9 交叉 3 次： 到目前为止生成的表
我虽然也许一个三维数组可以做到，但这对我来说似乎有点矫枉过正，而且肯定有一些已知的方法来处理这些情况。
一个（可能是其他许多）解决方案：
| 圆形\xtvt | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 铝 | BK | CJ | DI | EP | 佛 | GN | HM |
| 2 | PK | 阿杰 | 双 | 甲烷 | 做 | CN | 调频 | 总帐 |
| 3 | 橙汁 | PI | 啊 | BG | 中国 | DM | 埃尔 | FK |
| 4 | 你 | 哦 | PG | 自动对焦 | BM | CL | 丹麦 | EJ |
| 5 | 是 | 危险品 | 洛 | 杰米 | FI | 香港 | CP | 一个 |
| 6 | 光盘 | 英孚 | 锰 | 吉隆坡 | 生长激素 | AB | IJ | OP |
| 7 | 通用汽车 | LN | 东风 | EO | AK | J.P | BH | CI |
| 8 | 跳频 | 厘米 | EK | NP | 杰伦 | 胃肠道 | AO | BD |
用公式：
M3 : =IF(COUNTIFS($B$3:$I$10,$L3,$B$13:$I$20,M$2)=0,"",COUNTIFS($B$3:$I$10,$L3,$B$13:$I$20,M$2))
V3 : =IF(B3="","",COUNTIF($B$3:$I$10,B3))
AE3 : =COUNTIF($B3:$I3,AE$2)
并拖动到表格的末尾。
并将其映射到“Fill in team pair”表的第 1 行。我们将看到“xtvt number #”、“xtvt repeat watch”表计数将自动完成。我们只需要确保没有重复配对的团队（配对和 xtvt 都完成）。
“映射”我的意思是：在“填写团队配对”表中键入团队配对，并观察“xtvt 重复观看”表中的“填写”。一旦它充满了'1'，我们就完成了。
结果（现在）：
注意到“xtvt 重复观看”表中的类似差距，我将AN @ xtvt 8, round5。
然后我把BM @ xtvt 1,round5。但不能工作：
因为BM以前发生过。所以我们把BE。对其他人也重复同样的方法：寻找相似的差距，配对。做同样的另一对，我们将填满round5对..
请注意，“xtvt 重复手表”表是主要关注点。round6 的模式使用是：
恕我直言，这有点蛮力，但不太严格。完成这一步，我们将得到：
xtvt/team 的任何重复，我们可以在“xtvt repeat watch”表中看到“2”。如果我们得到 2，则表示该团队之前已经玩过 xtvt。
我想现在，我们可以看到这一步有点像填色书，使用与数独非常相似的思维步骤。
寻找可能
至于最后2轮，必须一起完成。只需同时填满两者，然后对其进行排序，以便没有团队在同一轮中重复（就像数独一样）。总结一下：
只是为了验证，使用“配对重复 chk”表并确保没有重复的团队配对。
我认为在某些时候要弄清楚这一点是不可能的。很高兴与大家分享找到的解决方案..
希望能帮助到你。
所以，即使@p. phidot已经提供了一个解决方案，我继续编写了一个可以解决它的程序。我这样做主要是因为我在 StackOverflow 上多次看到这个问题的各种版本，但很少有人得到满意的答案。
这里提出的问题是更一般的体育联盟调度问题的一个版本，其中重复桥牌锦标赛的豪厄尔和米切尔运动试图解决这个问题的不同变体。事实上，这是一个晦涩难懂的组合搜索问题，多年来在数学和计算机科学论文上做了一些工作（参见：1、2和3，它们似乎采用类似于 @ p.phidot的方法）
尽管有许多变体，但基本问题是在一个调度时间的矩形阵列内成对安排（“调度”）一组事物（“团队”）（“游戏”、“比赛”或“事件”） （一个“回合”）和一个独特的资源（Bridge 中的“句号”、“字段”或“板”，或上述问题中的“活动”）。这必须在以下常见的最小限制内完成：
通常，以下两个最小约束也很常见（尽管一些模糊的变体问题可能会改变这些）：
在这些几乎通用的规则之后，还有大量额外的约束产生了这个问题的所有许多变体。上面提出的问题就是我所说的“2x”问题，它具有以下附加限制：
从数值上讲，这强制要求附加规则，该规则也可以被视为用于编程和逻辑推理目的的伪约束：
虽然众所周知，一般问题的某些变体对于某些规模是可解决的，而其他变体则无法解决，但在大多数情况下，除了明显的数值冲突（例如团队太多/时间不足）之外，每个变体都足够不同，以至于通常不清楚哪些问题可以解决，哪些问题不能解决。例外情况就是我所说的“奇数规则”，如果任何参数（#Rounds、#Periods、#Teams）是奇数，那么通常可以通过简单地将团队和周期分别旋转不同的数量来解决圆形的。但是，这不适用于所有偶数，因为通过简单的轮换，球队的对手或周期将在中途重复。这意味着当所有参数都是偶数时，有'如果它可以解决它变得更像一个数独谜题。
因此，我编写了这个程序来解决上述问题的版本，使用有限形式的分支定界组合搜索技术。好消息是它可以解决 OP 提出的具体问题（8 轮，8 节，16 支队伍），这是它给出的答案：
| 周期\圆形 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0,1 | 3,5 | 2,4 | 6,8 | 7,12 | 10,14 | 9,13 | 11,15 |
| 1 | 3,4 | 0,2 | 1,5 | 7,9 | 6,14 | 8,15 | 11,12 | 10,13 |
| 2 | 2,5 | 1,4 | 0,3 | 12,15 | 8,13 | 7,11 | 6,10 | 9,14 |
| 3 | 6,7 | 8,10 | 9,11 | 0,4 | 1,15 | 3,13 | 2,14 | 5,12 |
| 4 | 8,9 | 6,11 | 7,10 | 13,14 | 0,5 | 1,12 | 4,15 | 2,3 |
| 5 | 10,11 | 12,14 | 13,15 | 1,2 | 3,9 | 0,6 | 5,8 | 4,7 |
| 6 | 12,13 | 9,15 | 8,14 | 3,10 | 2,11 | 4,5 | 0,7 | 1,6 |
| 7 | 14,15 | 7,13 | 6,12 | 5,11 | 4,10 | 2,9 | 1,3 | 0,8 |
（显然，我已经从零开始编号）
现在是坏消息：实际上，它最多只能运行 9 轮。对于 10 轮及以上，它基本上永远运行（我已经让它运行了几个小时而没有完成）。所以如果有人想用它来解决更大的问题，就需要进行更多的优化（更新：11 轮它大约在一天内完成。对于 12 轮，我估计需要大约一年）。但请记住，无论奇数有多大，手动求解总是很容易。
所以这是主要的求解器类（所有代码都在 c# 中）：
class SLSx2Solver
{
public int NumTeams { get; internal set; }
public int NumRounds { get; internal set; }
public int NumPeriods { get; internal set; }
public Schedule State;
public SLSx2Solver(int teams, int rounds, int periods)
{
NumRounds = rounds;
NumPeriods = rounds;
NumTeams = 2 * rounds;
}
public Schedule SolveIt()
{
State = new Schedule(NumTeams, NumRounds, NumPeriods);
// To remove as many solution symmetries as possible before doing
// the BnB search, fully specify the first team's schedule arbitrarily
for (int round = 0; round < NumRounds; round++)
{
State.AddPairing(0, round + 1, round, round);
}
// test all possible assignments for each round, in order
bool solutionWasFound = SolveRemainingRounds(State, 0);
return State;
}
// Try all possible assignments for this round and any remaining rounds.
// Returns true if it was able to find a solution.
internal bool SolveRemainingRounds(Schedule state, int round)
{
// check if all rounds have been finished
if (round >= state.NumRounds)
{
return state.IsSolved;
}
if (state.RoundHasUnassignedTeams(round))
{
if (AssignRemainingPeriods(state, round, 0))
{
return true; // current assignments worked, so cascade it back
}
return false; // current path found no solutions
}
else
{
if(state.RoundIsComplete(round))
{
return SolveRemainingRounds(state, round + 1);
}
return false; // current path found no solutions
}
}
// Test all possible assignments for this period, then all remaining
// periods in the round. Returns true if a solution was found.
internal bool AssignRemainingPeriods(Schedule state, int round, int period) //, List<int> teams = null, int teamIdx = 0)
{
// Is the Round done?
if (state.RoundIsComplete(round))
{
// move to the next round
return SolveRemainingRounds(state, round + 1);
}
// there has to be unassinged teams
List<int> teams = state.RoundUnassignedTeams(round);
if (teams == null || teams.Count == 0)
{
throw new Exception("AssignRemainingPeriods(" + round.ToString() + "): no unassigned teams!");
}
// find the first unassigned Period, starting from (period)
do
{
if (state.RoundPeriod(round, period) == null) break;
period++;
} while (period < state.NumPeriods);
if (period >= state.NumPeriods)
{
throw new Exception("AssignRemainingPeriods(" + round.ToString() + "): no unassigned periods!");
}
// try all combinations of the unassigned teams, in order
for (int teamIdx = 0; teamIdx < teams.Count - 1; teamIdx++)
{
int team1 = teams[teamIdx];
// before we try all team2 combinations, make sure team1
// hasn't already used this period
if (!state.TeamUsedPeriod(team1, period))
{
// try all higher unassigned teams
for (int idx2 = teamIdx + 1; idx2 < teams.Count; idx2++)
{
int team2 = teams[idx2];
if (state.AddPairing(team1, team2, round, period))
{
// assign the next team pair
bool found = AssignRemainingPeriods(state, round, period + 1);
if (found)
{
return true;
}
else
{
// undo the period-assignment
state.UndoPairing(team1, team2, round, period);
}
}
}
}
}
// no complete assignments found on this branch
return false;
}
}
此代码在 Schedule 对象上实现品牌和绑定样式递归，该对象以一种 4 维（Rounds x Periods x Team1 vs Team2）稀疏数组“空心制表立方体”结构保存和跟踪调度分配，我觉得这很有用用于解决8 皇后问题的类型（即，每个维度中出现一个对象）。该类的代码在这里：
class Schedule
{
// The public-readable attributes (immutable)
public int NumTeams { get; internal set; } // Max 32
public int NumRounds { get; internal set; } // Max 32
public int NumPeriods { get; internal set; }
public Schedule(int teams, int maxRounds, int periods)
{
NumTeams = teams;
NumRounds = maxRounds;
NumPeriods = periods;
// initialize the search-state
// (could make this a 4-dimensional array, but it would be HUGE)
roundXperiod = new Assignment[NumRounds, NumPeriods];
periodXteam = new Assignment[NumPeriods, NumTeams];
roundXteam = new Assignment[NumRounds, NumTeams];
teamXteam = new Assignment[NumTeams, NumTeams];
periodsAssignedCount = new int[NumRounds];
teamsAssignedCount = new int[NumRounds];
// init the moves-log stack
assignments = new Stack<Assignment>((NumTeams + 1 * NumRounds) / 2);
}
#region Internal Assignment-tracking structures
Assignment[,] roundXperiod;
Assignment[,] periodXteam;
Assignment[,] roundXteam;
Assignment[,] teamXteam; // [team1,team2] | team1 < team2
int[] periodsAssignedCount;
int[] teamsAssignedCount;
int roundsComplete;
#endregion
#region State-checking public interface
public bool RoundHasUnassignedTeams(int round)
{
return teamsAssignedCount[round] < NumTeams;
}
public bool RoundIsComplete(int round)
{
if (periodsAssignedCount[round] == NumPeriods
&& teamsAssignedCount[round] == NumTeams)
return true;
else
return false;
}
public bool IsSolved { get { return (roundsComplete == NumRounds); } }
public Assignment RoundPeriod(int round, int period)
{
return roundXperiod[round, period];
}
public bool TeamUsedPeriod(int team, int period)
{
return (periodXteam[period, team] != null);
}
#endregion
#region public List Generation
public List<int> RoundUnassignedTeams(int round)
{
List<int> lst = new List<int>();
for (int t = 0; t < NumTeams; t++)
{
if (roundXteam[round, t] == null)
lst.Add(t);
}
return lst;
}
public List<int> RoundUnassignedPeriods(int round)
{
List<int> lst = new List<int>();
for (int p = 0; p < NumPeriods; p++)
{
if (roundXperiod[round, p] == null)
lst.Add(p);
}
return lst;
}
#endregion
#region Schedule Assignment public interface
public bool AddPairing(int team1, int team2, int round, int period)
{
Assignment move = new Assignment(team1, team2, round, period);
return Push(move);
}
public void UndoPairing(int team1, int team2, int round, int period)
{
// do some validity checking
Assignment move = Peek();
if (move == null
|| move.Team1 != team1
|| move.Round != round
|| move.Team2 != team2
|| move.Period != period
)
throw new Exception("Schedule.UndoPairing: does not match last move!");
Pop();
return;
}
#endregion
#region Schedule-assignment internal implementation
Stack<Assignment> assignments;
// Adds an assignment to the search state, returns false if the
// assignmment was invalid. (All of the delta-logic is here)
bool Push(Assignment evnt)
{
/* Everything needs to be checked first */
// Has team1 already been assigned?
if (roundXteam[evnt.Round, evnt.Team1] != null) return false;
// Has team1 already used this period?
if (periodXteam[evnt.Period, evnt.Team1] != null) return false;
// Is the round-period unassigned?
if (roundXperiod[evnt.Round, evnt.Period] != null) return false;
// Has team2 already used this period?
if (periodXteam[evnt.Period, evnt.Team2] != null) return false;
// Is team2 unassinged for this round?
if (roundXteam[evnt.Round, evnt.Team2] != null) return false;
// Have these two teams already played each other?
if (teamXteam[evnt.Team1, evnt.Team2] != null) return false;
// Add the move to the stack
assignments.Push(evnt);
/* Make all changes to the data-structures */
roundXteam[evnt.Round, evnt.Team1] = evnt;
teamsAssignedCount[evnt.Round]++;
periodXteam[evnt.Period, evnt.Team1] = evnt;
roundXperiod[evnt.Round, evnt.Period] = evnt;
periodsAssignedCount[evnt.Round]++;
roundXteam[evnt.Round, evnt.Team2] = evnt;
teamsAssignedCount[evnt.Round]++;
periodXteam[evnt.Period, evnt.Team2] = evnt;
teamXteam[evnt.Team1, evnt.Team2] = evnt;
if (RoundIsComplete(evnt.Round)) roundsComplete++;
return true;
}
// UnDo whatever the last move (on top of the stack) was
// (this is where all of the state-UnDo logic needs to be)
void Pop()
{
Assignment evnt = assignments.Pop();
/* validate first */
if (roundXteam[evnt.Round, evnt.Team1] == null
|| roundXteam[evnt.Round, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: teamAssignment[Team1] does not match!");
if (periodXteam[evnt.Period, evnt.Team1] == null
|| periodXteam[evnt.Period, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: periodTeams[Period,Team1] does not match!");
// Is the round-period matching?
if (roundXperiod[evnt.Round, evnt.Period] == null
|| roundXperiod[evnt.Round, evnt.Period] != evnt)
throw new Exception("Schedule.Pop: periodAssignments does not match!");
if (periodXteam[evnt.Period, evnt.Team2] == null
|| periodXteam[evnt.Period, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: periodTeams[Period,Team2] does not match!");
if (roundXteam[evnt.Round, evnt.Team2] == null
|| roundXteam[evnt.Round, evnt.Team2] != evnt)
throw new Exception("Schedule.Pop: teamAssignment[Team2] does not match!");
if (teamXteam[evnt.Team1, evnt.Team2] == null
|| teamXteam[evnt.Team1, evnt.Team2] != evnt)
throw new Exception("Schedule.Pop: team1VsTeam2[Team1,Team2] does not match!");
// Implement UnDO
bool wasComplete = RoundIsComplete(evnt.Round);
roundXteam[evnt.Round, evnt.Team1] = null;
teamsAssignedCount[evnt.Round]--;
periodXteam[evnt.Period, evnt.Team1] = null;
roundXperiod[evnt.Round, evnt.Period] = null;
periodsAssignedCount[evnt.Round]--;
periodXteam[evnt.Period, evnt.Team2] = null;
roundXteam[evnt.Round, evnt.Team2] = null;
teamsAssignedCount[evnt.Round]--;
teamXteam[evnt.Team1, evnt.Team2] = null;
if (wasComplete
&& !RoundIsComplete(evnt.Round)) roundsComplete--;
return;
}
Assignment Peek()
{
return assignments.Peek();
}
#endregion
public override string ToString()
{
string str = "P \\ R->";
for (int r = 0; r < NumRounds; r++)
{
str += "\t" + r.ToString();
}
str += "\n";
for (int p = 0; p < NumPeriods; p++)
{
str += p.ToString();
for (int r = 0; r < NumRounds; r++)
{
str += "\t" + ((roundXperiod[r, p]?.PairString)??"");
}
str += "\n";
}
return str;
}
}
最后，上述两个类都使用Assignment封装了两支球队在特定回合和时间段内相互比赛的对象：
public class Assignment
{
// Create a schedule pairing assignment
public Assignment(int team1, int team2, int round, int period)
{
if (team2 == -1 || period == -1)
throw new Exception("Cannot create a Pairing Assingment if team2 or period = -1");
// by convetion, Team1 must always be less than Team2
if (team1 < team2)
{
Team1 = team1;
Team2 = team2;
}
else
{
Team1 = team2;
Team2 = team1;
}
Round = round;
Period = period;
}
public int Team1 { get; internal set; }
public int Team2 { get; internal set; }
public int Round { get; internal set; }
public int Period { get; internal set; }
public string PairString
{
get
{
return Team1.ToString() + "," + Team2.ToString();
}
}
}
下面是我的表单中的一些代码，说明了如何使用求解器类：
listBox1.Items.Clear();
listBox1.Items.Add(" ... running ...");
SLSx2Solver slv = new SLSx2Solver(rounds);
Schedule sol = slv.SolveIt();
if (!sol.IsSolved)
{
MessageBox.Show("No Solution Found.", "Solution Result:", MessageBoxButtons.OK, MessageBoxIcon.Information);
return;
}
// display the results
listBox1.Items.Clear();
string str = sol.ToString();
foreach(string s in str.Split('\n'))
{
listBox1.Items.Add(s);
}
NumTeams = teams;