配对团队

Question

数据库包含团队列表，每个团队都按位置分隔(西部团队、东部团队等)。有两种类型的事实来描述这一点。团队(TeamNumber，Losses)和区域(TeamNumber，Region)。例如：

team(1, 10).
team(2, 11).
team(3, 12).
team(4, 13).

region(1, east).
region(2, west).
region(3, east).
region(4, southeast).

注意:团队列表并不总是从损失最少到损失最多的顺序排列。

我正在尝试将一组团队配对在一起，以便将损失最高的团队与损失最低的团队配对，然后将损失第二高的团队与损失第二少的团队配对，然后将ecetera ecetera配对。规则是，在相同区域内配对团队是优先事项。在上面的示例中，团队3和1将配对在一起，因为他们都是东部团队。现在，剩下的团队是团队2和团队4。但因为没有其他团队在他们的区域内，团队2和团队4相互匹配。

现在，我在想我可以写什么函数来配对团队。我已经编写了一个函数，将一个区域内的所有不同团队分组到一个相应的列表中。我还编写了一个函数来获取最小值和最大值(最高和最低损失)。

我如何编写一个函数来将同一区域内的所有团队配对，然后创建一个新的列表来粘贴该列表中的所有剩余团队？

Answer 1

我还写了一个函数来得到最小值和最大值(最高和最低损失)。

Prolog和其他声明性语言在一些令人惊讶的方面与过程性语言不同，其中之一是经常做一点工作，期望在某种循环构造中重用它，这并不完全是正确的方法。这在SQL中更为明显，在SQL中，您应该始终处理集合，但在Prolog中也是如此，在Prolog中，我们拥有的少量显式循环构造并未大量使用。

在程序环境中匹配低分和高分团队的问题最好通过如下过程来解决：

def match(teams):
  while we have teams:
    remove the lowest scoring team from teams
    remove the highest scoring team from teams
    save this pair
  return the list of pairs

一种使其更具功能性的天真方法是使用递归：

def match(teams):
  if teams is empty: return empty list
  otherwise:
    remove the lowest scoring team
    remove the highest scoring team
    return this pair appended to match(teams without these two items)

实际上，你可以不费很多力气就把它转换成看起来合理的Prolog：

match([], []).
match(Teams, [Lowest-Highest|Pairs]) :-
  lowest(Teams, Lowest),
  highest(Teams, Highest),
  select(Lowest, Teams, TeamsWithoutLowest),
  select(Highest, TeamsWithoutLowest, RemainingTeams),
  match(RemainingTeams, Pairs).

这不太可能是高效的，因为在select/3中有许多重复的列表扫描和大量的列表重建正在进行，但它可能更具声明性。

另一种方法是对团队列表进行排序，然后将其折叠起来，以获得最低和最高的配对。视觉上：

[1, 2, 3, 4, 5, 6]
[1, 2, 3],  [4, 5, 6]
[1, 2, 3],  [6, 5, 4]

[1,     2,     3]
[6,     5,     4]
-------------------
[1-6], [2-5], [3-4]

我们可以直接在Prolog中做这件事，但首先我们需要一种将两个列表配对的方法：

pair_off([], _, []).
pair_off([L|Ls], [R|Rs], [L-R|Rest]) :- pair_off(Ls, Rs, Rest).

然后算法转到Prolog，如下所示：

match_lowest_highest(SortedList, Pairs) :-
  length(SortedList, N2),
  N is N2 div 2,
  length(TopHalf, N),
  append(TopHalf, BottomHalf, SortedList),
  reverse(BottomHalf, BottomHalfFlipped),
  pair_off(TopHalf, BottomHalfFlipped, Pairs).

这仍然不是很有效，但reverse/2内置可能正在使用差异列表，所以它应该不会太昂贵；通过将append/3与已实体化的未知数列表一起使用，我们节省了一大堆临时列表构造，这些构造可能会被丢弃。因此，我不认为这是非常低效的，但我相信有其他方法可以做到这一点会更有效率。

Answer 2

好吧，我试过了。我认为all_ teams _ paired /2将提供您所描述的所有配对的团队的列表，以及剩余的团队(如果有奇数个团队)。

% list of all regions
regions(Regions) :- 
    findall(Region, region(_, Region), UnsortedRegions),
    sort(UnsortedRegions, Regions).

% list of all teams in a region
teams_in_region(Region, Teams) :- findall(Team, (team(Team, _), region(Team, Region)), Teams).

% bottom team in a list
bottom_team(TeamList, BottomTeam) :-
    member(BottomTeam, TeamList),
    findall(Losses, (team(Team, Losses), member(Team, TeamList)), AllLosses),
    team(BottomTeam, Losses),
    min_member(Losses, AllLosses).

% top team in a list
top_team(TeamList, TopTeam) :-
    member(TopTeam, TeamList),
    findall(Losses, (member(Team, TeamList), team(Team, Losses)), AllLosses),
    team(TopTeam, Losses),
    max_member(Losses, AllLosses).

% teams are paired with the top loser playing the bottom loser and there can be a leftover
%  if there is an odd number of teams
paired_teams([], [], []).
paired_teams([LonelyTeam], [], [LonelyTeam]).
paired_teams(TeamList, PairedTeams, UnpairedTeam) :-
    top_team(TeamList, TopTeam),
    bottom_team(TeamList, BottomTeam),
    TopTeam \= BottomTeam,
    subtract(TeamList, [TopTeam, BottomTeam], RemainingTeams),
    paired_teams(RemainingTeams, RemainingPairedTeams, UnpairedTeam),
    append([TopTeam-BottomTeam], RemainingPairedTeams, PairedTeams).

% a list of regions has an associated list of paired teams and leftover teams
region_paired_teams([], [], []).
region_paired_teams(Regions, PairedTeams, UnpairedTeams) :-
    Regions = [Region|RemainingRegions],
    teams_in_region(Region, TeamList),
    paired_teams(TeamList, RegionPairedTeams, RegionUnpairedTeam),
    region_paired_teams(RemainingRegions, RemainingPairedTeams, RemainingUnpairedTeams),
    append(RegionPairedTeams, RemainingPairedTeams, PairedTeams),
    append(RegionUnpairedTeam, RemainingUnpairedTeams, UnpairedTeams).

% a list of all teams paired with priority given to region and a leftover team (if any)
all_teams_paired(TeamsPaired, Leftover) :-
    regions(Regions),
    region_paired_teams(Regions, RegionPairedTeams, UnpairedTeams),
    paired_teams(UnpairedTeams, NonRegionPairedTeams, Leftover),
    append(RegionPairedTeams, NonRegionPairedTeams, TeamsPaired).

我是否正确理解了您的要求？