algorithm - 如何计算列表的特定组合？ (对接会)

Question

我的一个 friend 参加 Volley 联赛，向我提出了一个有趣的问题:

以下每个字母代表一对玩家

; player pairs (24)
'(a b c d e f g h i j k l m n o p q r s t u v w x)

创建比赛，其中 3 对组合成一个团队(一个团队中有 6 个玩家)

; teams
'((a b c) (d e f) (g h i) (j k l) (m n o) (p q r) (s t u) (v w x))

团队的组合将组成一场比赛

; matches
'(((a b c) (d e f))
  ((g h i) (j k l))
  ((m n o) (p q r))
  ((s t u) (v w x)))

在一个给定的晚上，他们可能会打 8 到 12 场比赛， 但在每场比赛之前，这对球员将随机 .主持人的意图是尽可能地洗牌，但结果往往远非良好的分配。 'a将与 'b 配对太多次等等。

在 '(a b c) 的场景中组队，理想情况下 'a不会在有 'b 的团队中踢球或 'c再次。同样， 'b不会再玩 'c ， 如果可能的话。

简单计算 C(24 选择 3) 的组合，就有 2,024 个可能的团队......

'((a b c)
  (a b d)
  (a b e)
  ...)`

我在想我可以过滤掉非完全独特的团队组合，但这并不能真正让我更接近我的解决方案。

考虑以下两个

'(a b c) ; team1
'(a w x) ; team2

这是两个完全独特的团队组合，但我们当然不能将它们放在比赛中，因为对 'a不可能同时在两支球队比赛。因此，这些团队组合决不应该在单个比赛解决方案中提供。

另一个问题是，玩家对可能不能被 6 整除。

; player pairs (26)
'(a b c d e f g h i j k l m n o p q r s t u v w x y z)

; teams
'((a b c) (d e f) (g h i) (j k l) (m n o) (p q r) (s t u) (v w x))

; matches
'(((a b c) (d e f))
  ((g h i) (j k l))
  ((m n o) (p q r))
  ((s t u) (v w x)))

; sit-out this game
'(y z)

问题一:

如何生成由独特团队组合组成的所有可能匹配的列表？

问题二:

如何扩展算法以适应“坐下”的玩家。如果球员对的列表不能被 6 整除，则每对球员必须参加相等数量的比赛。

--

所以我没有太多代码可以展示，因为我一直在死胡同。我得到的最远的是 X choose Y这样我就有了所有可能的团队组合的列表。我在过滤掉非完全唯一的组合时遇到了麻烦。即使我成功了，我也不知道如何将完全独特的组合组合成匹配​​。

答案不必包括完整的实现，但指出我正确的方向会很有帮助。我对这种计算没有太多经验。

Answer 1

您可以使用 combinations 构建问题 1 的解决方案。功能和一些额外的过滤。首先是一些数据定义:

;; A Player-Pair is a Symbol.
;; A Team is a (List Player-Pair Player-Pair Player-Pair).
;; A Match is a (List Team Team) where the teams are disjoint.

;; Player-Pairs : (Listof Player-Pair)
(define player-pairs '(a b c d e f g h i j k l m n o p q r s t u v w x))

所以，我们想要的是找到比赛，但要做到这一点，我们需要从 3 个玩家对的所有组合中找到一组球队，然后对其进行过滤，以满足您的约束，即两个玩家对永远不应该不止一次地在一个团队中。

我还不知道怎么做，但这听起来很复杂，所以让它成为一个名为 filter-team-combinations 的辅助函数.

;; find-teams : (Listof Player-Pair) -> (Listof Team)
(define (find-teams player-pairs)
  (filter-team-combinations (combinations player-pairs 3)))

;; filter-team-combinations : (Listof Team) -> (Listof Team)
;; Filters out teams where a player-pair would on a team with another
;; player-pair for the second time.
(define (filter-team-combinations teams) ....)

嗯。要知道给定的 Team有两对已经一起加入球队的球员，我也需要跟踪这一点。它可能会是递归的，并且已经在一起的玩家对将从一个递归调用更改为下一个。当我们添加到结果列表中时，pair-pairs 的列表会变大。所以我们需要将它作为一个参数添加，它以一个空列表开始。

;; find-teams : (Listof Player-Pair) -> (Listof Team)
(define (find-teams player-pairs)
  (filter-team-combinations (combinations player-pairs 3) (list)))

;; A Pair-Pair is a (List Player-Pair Player-Pair)

;; filter-team-combinations : (Listof Team) (Listof Pair-Pair) -> (Listof Team)
;; Filters out teams where a player-pair would on a team with another
;; player-pair for the second time.
;; pair-pairs is an accumulator that stores the pair-pairs that we've
;; seen so far.
(define (filter-team-combinations teams pair-pairs) ....)

filter-team-combinations函数处理一个团队列表，一个列表可以是空的，也可以是第一个团队让给其余团队:

(define (filter-team-combinations teams pair-pairs)
  (cond [(empty? teams) ....]
        [else .... (first teams) .... (rest teams) ....]))

对于基本情况，如果没有要过滤的团队，我们将返回空列表。对于递归情况，它必须查看第一队包含的球员对，检查它们是否与现有的 pair-pairs 冲突。 ，并以此为基础:

(define (filter-team-combinations teams pair-pairs)
  (cond [(empty? teams) (list)]
        [else
         (define new-pair-pairs (combinations (first teams) 2))
         (cond [(pair-pairs-conflict? new-pair-pairs pair-pairs)
                .... (first teams) .... (rest teams) ....]
               [else
                .... (first teams) .... (rest teams) ....])]))

;; pair-pairs-conflict? : (Listof Pair-Pair) (Listof Pair-Pair) -> Boolean
(define (pair-pairs-conflict? as bs) ....)

所以，假装 pair-pairs-conflict?做正确的事，我们将填写 .... s 完成 filter-team-combinations .在它们发生冲突的情况下，我们应该放弃第一支队伍并在其余的队伍上重新开始。在他们不冲突的情况下，我们应该让第一支球队去做一些事情。

(define (filter-team-combinations teams pair-pairs)
  (cond [(empty? teams) (list)]
        [else
         (define new-pair-pairs (combinations (first teams) 2))
         (cond [(pair-pairs-conflict? new-pair-pairs pair-pairs)
                ;; This team has a pair-pair that a previous team already had,
                ;; so don't include this team in the result; recur on the rest.
                (filter-team-combinations (rest teams) pair-pairs)]
               [else
                ;; Cons this team onto something.
                (cons (first teams)
                      ....)])]))

最后 .... ，我们需要对其余部分进行递归，但我们还需要确保递归调用知道第一支球队中的球员对不应该再次出现在同一支球队中。为此，我们可以将它们附加到 pair-pairs争论。

;; filter-team-combinations : (Listof Team) (Listof Pair-Pair) -> (Listof Team)
;; Filters out teams where a player-pair would on a team with another
;; player-pair for the second time.
;; pair-pairs is an accumulator that stores the pair-pairs that we've
;; seen so far.
(define (filter-team-combinations teams pair-pairs)
  (cond [(empty? teams) (list)]
        [else
         (define new-pair-pairs (combinations (first teams) 2))
         (cond [(pair-pairs-conflict? new-pair-pairs pair-pairs)
                ;; This team has a pair-pair that a previous team already had,
                ;; so don't include this team in the result; recur on the rest.
                (filter-team-combinations (rest teams) pair-pairs)]
               [else
                ;; Add this team and add the new pair-pairs.
                (cons (first teams)
                      (filter-team-combinations (rest teams)
                                                (append new-pair-pairs pair-pairs)))])]))

所以现在我们需要实现 pair-pairs-conflict?谓词。

;; pair-pairs-conflict? : (Listof Pair-Pair) (Listof Pair-Pair) -> Boolean
;; A team must be made up of sets of player-pairs that haven't been on the
;; same team yet. This function takes two lists of player-pair pairs.
;; Each pair-pair in the first list has two player-pairs that would now be
;; on the same team.
;; Each pair-pair in the second list has two player-pairs that have been
;; on the same team already.
;; This function returns true iff any player-pair would be on the same
;; team with anyone they have already been on the same team with.
(define (pair-pairs-conflict? as bs) ....)

它需要取 as 中的每一对pair并检查它是否在 bs ，如果有冲突， a在 bs .一种方法是使用 ormap ，另一种方法是使用 for/or .

(define (pair-pairs-conflict? as bs)
  (for/or ([a (in-list as)])
    (member a bs)))

但这有一个问题。对对 (list 'a 'b)应视为与pair-pair (list 'b 'a) 相同.所以我们需要一个 member不关心这个排序的函数。幸运的是， member可以将第三个参数用作相等谓词。

(define (pair-pairs-conflict? as bs)
  (for/or ([a (in-list as)])
    (member a bs pair-pair=?)))

;; pair-pair=? : Pair-Pair Pair-Pair -> Boolean
(define (pair-pair=? a b)
  (match-define (list a1 a2) a)
  (match-define (list b1 b2) b)
  (or (and (equal? a1 b1) (equal? a2 b2))
      (and (equal? a1 b2) (equal? a2 b1))))

现在我们拥有了找到所有有效团队所需的一切。

(define teams (find-teams player-pairs))

为了找到比赛，我们需要两支球队的组合，但我们需要过滤它们以确保球队是不相交的，这样一对球员就不会与自己对抗。

;; find-matches : (Listof Team) -> (Listof Match)
(define (find-matches teams)
  (filter match-has-disjoint-teams? (combinations teams 2)))

;; match-has-disjoint-teams? : Match -> Boolean
(define (match-has-disjoint-teams? match)
  (teams-disjoint? (first match) (second match)))

;; teams-disjoint? : Team Team -> Boolean
(define (teams-disjoint? team-1 team-2) ....)

实现 teams-disjoint? ，我们需要匹配 team-1 中的每个玩家对对抗 team-2 中的每个玩家对并确保它们都不相等。一种方法是使用 cartesian-product和 andmap ，但另一种方法是使用 for*/and .

;; teams-disjoint? : Team Team -> Boolean
(define (teams-disjoint? team-1 team-2)
  (for*/and ([p1 (in-list team-1)]
             [p2 (in-list team-2)])
    (not (equal? p1 p2))))

使用 find-matches :

> (find-matches (list (list 'a 'b) (list 'b 'c) (list 'c 'd) (list 'd 'a)))
(list (list (list 'a 'b) (list 'c 'd))
      (list (list 'b 'c) (list 'd 'a)))
> (find-matches (list (list 'a 'b 'c)
                      (list 'c 'd 'e)
                      (list 'e 'f 'g)
                      (list 'g 'h 'i)))
(list (list (list 'a 'b 'c) (list 'e 'f 'g))
      (list (list 'a 'b 'c) (list 'g 'h 'i))
      (list (list 'c 'd 'e) (list 'g 'h 'i)))

我对问题 1 的尝试解决方案是编写 find-matches与 find-teams :

(find-matches (find-teams player-pairs))

使用 24 对不同的玩家对，这会产生 1,624 种不同的比赛。

虽然，虽然两个球员对永远不会在不同的球队中在一起，但这包括与他们在不同比赛中的同一支球队在一起的比赛。

这可能不是你想要的。不过，它可能会帮助您到达那里，所以无论如何我都会发布它。