如何查找所有两个列表对，并对它们进行分类而不重复？

Question

我们正在准备一个计划，其中18个人应该以一种方式讨论主题，在每一轮中他们形成对，然后他们切换，直到每个人都与每个人交谈。这意味着共有153个讨论，每轮9对并行，共17轮。我试图制定一个矩阵，显示谁应该与谁交谈，以避免混乱，但不能成功。为简单起见，每个人都有一个数字，所以底线是，我需要所有数字组合从1到18（用组合函数做），但是这些对应该重新排列为17轮这样每个数字每轮只出现一次。有任何想法吗？

Answer 1

让我们首先看看6人的一个更简单的问题。以下矩阵列出了谁（行）与谁（列）在哪一轮（条目）中交谈：

因此，例如在第1轮（黄色）中，我们有以下对：

(1-2), (3-5), (4-6)

对于第2轮（绿色），我们将：

(1-3), (2-6), (4-5)

等等。

因此，基本上我们正在寻找对称拉丁方（即在每一行和每列中每个条目仅出现一次，参见Latin Squares on Wikipedia）。

方框中的拉丁方可以通过附加表轻松生成：

inner_ls <- function(k) {
  res <- outer(0:(k-1), 0:(k-1), function(i, j) (i + j) %% k)
  ## replace zeros by k
  res[res == 0] <- k
  ## replace diagonal by NA
  diag(res) <- NA
  res
}

inner_ls(5)
#      [,1] [,2] [,3] [,4] [,5]
# [1,]   NA    1    2    3    4
# [2,]    1   NA    3    4    5
# [3,]    2    3   NA    5    1
# [4,]    3    4    5   NA    2
# [5,]    4    5    1    2   NA

所以剩下的就是在最后一行（列）附加缺少的轮数：

full_ls <- function(k) {
  i_ls <- inner_ls(k - 1)
  last_row <- apply(i_ls, 1, function(row) {
    rounds <- 1:(k - 1)
    rounds[!rounds %in% row]
  })
  res <- cbind(rbind(i_ls, last_row), c(last_row, NA))
  rownames(res) <- colnames(res) <- 1:k
  res
}

full_ls(6)

#    1  2  3  4  5  6
# 1 NA  1  2  3  4  5
# 2  1 NA  3  4  5  2
# 3  2  3 NA  5  1  4
# 4  3  4  5 NA  2  1
# 5  4  5  1  2 NA  3
# 6  5  2  4  1  3 NA

有了它，你得到你的分配矩阵如下：

full_ls(18)

#     1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
# 1  NA  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
# 2   1 NA  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17  2
# 3   2  3 NA  5  6  7  8  9 10 11 12 13 14 15 16 17  1  4
# 4   3  4  5 NA  7  8  9 10 11 12 13 14 15 16 17  1  2  6
# 5   4  5  6  7 NA  9 10 11 12 13 14 15 16 17  1  2  3  8
# 6   5  6  7  8  9 NA 11 12 13 14 15 16 17  1  2  3  4 10
# 7   6  7  8  9 10 11 NA 13 14 15 16 17  1  2  3  4  5 12
# 8   7  8  9 10 11 12 13 NA 15 16 17  1  2  3  4  5  6 14
# 9   8  9 10 11 12 13 14 15 NA 17  1  2  3  4  5  6  7 16
# 10  9 10 11 12 13 14 15 16 17 NA  2  3  4  5  6  7  8  1
# 11 10 11 12 13 14 15 16 17  1  2 NA  4  5  6  7  8  9  3
# 12 11 12 13 14 15 16 17  1  2  3  4 NA  6  7  8  9 10  5
# 13 12 13 14 15 16 17  1  2  3  4  5  6 NA  8  9 10 11  7
# 14 13 14 15 16 17  1  2  3  4  5  6  7  8 NA 10 11 12  9
# 15 14 15 16 17  1  2  3  4  5  6  7  8  9 10 NA 12 13 11
# 16 15 16 17  1  2  3  4  5  6  7  8  9 10 11 12 NA 14 13
# 17 16 17  1  2  3  4  5  6  7  8  9 10 11 12 13 14 NA 15
# 18 17  2  4  6  8 10 12 14 16  1  3  5  7  9 11 13 15 NA