0

データベースにはチームのリストが含まれており、これらの各チームは場所 (西チーム、東チームなど) で区切られています。これを説明するには、2 種類の事実があります。team(TeamNumber, Losses) と region(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).

注: チームのリストは、常に損失が少ないものから多いものへと並べられるとは限りません。

チームのリストを組み合わせて、損失が最も多いチームが損失が最も少ないチームとペアになり、次に損失が2番目に多いチームが損失が2番目に少ないチームとペアになるようにしようとしています、およびecetera ecetera。ルールは、同じ地域内のペアを組むことです。上記の例では、チーム 3 と 1 はどちらも東チームであるため、ペアになります。ここで、残りのチームはチーム 2 と 4 です。しかし、他のチームがその地域にないため、チーム 2 と 4 が互いに対戦します。

今、私はチームをペアにするためにどのような関数を書くことができるかを考えています. 地域内のすべての異なるチームを対応するリストにグループ化する関数を既に作成しました。また、最小値と最大値 (最大損失と最小損失) を取得する関数も作成しました。

同じ地域内のすべてのチームをペアにする関数を作成し、そのリスト内の残りのすべてのチームを貼り付ける新しいリストを作成するにはどうすればよいですか?

4

2 に答える 2

2

また、最小値と最大値 (最大損失と最小損失) を取得する関数も作成しました。

Prolog やその他の宣言型言語は、いくつかの驚くべき方法で手続き型言語とは異なります。そのうちの 1 つは、ある種のループ構造内から再利用することを予期して、作業の一部を頻繁に実行することは、正確には正しいアプローチではないということです。これは、常にセットの観点から処理する必要がある SQL ではより明らかに当てはまりますが、明示的なループ構造があまり使用されていない 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 つの方法は、チームのリストを並べ替えてから、それを元に戻して、最下位と最上位のペアを取得することです。視覚的に:

[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 でいくらか直接行うことができますが、最初に 2 つのリストをペアにする方法が必要です。

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すでに実体化された未知数のリストを使用することで、破棄される一時的なリスト構築の束を節約できます。したがって、これがひどく非効率的であるとは思いませんが、より効率的な方法が他にもあると確信しています。

于 2013-03-04T04:13:13.063 に答える