时间戳

首页 > 解决方案 > 如何找到两个列表的所有对，并在不重复的情况下对它们进行分类？

r - 如何找到两个列表的所有对，并在不重复的情况下对它们进行分类？

问题描述

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

标签： rcombinatorics

解决方案

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

分配矩阵

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

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

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

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

等等。

因此，基本上我们正在寻找一个对称的拉丁方格（即在每一行和每一列中，每个条目只出现一次，参见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

推荐阅读