使用行和列R唯一的条目创建矩阵

Question

我需要在R中找到每行和每列唯一的整数1-5的所有可能的5x5矩阵(想象一个数独(。

在不创建所有120C5矩阵然后找到合适的矩阵的情况下，有什么有效的方法可以做到这一点吗？

谢谢！

Answer 1

正如我在上面的评论中所说，这种类型的矩阵被称为拉丁正方形。

首先，我们已经知道有56个所谓的缩小拉丁正方形和161280个大小为5的全拉丁正方形。缩减的拉丁正方形使得第一列和第一行都只有1、2、3、4、5(按此顺序(。给定这些缩小的拉丁正方形，可以很容易地(只要大小不大于5(生成所有拉丁正方形：排列除第一行外的所有行，排列所有列。因此，正如预期的那样，161280=5*4*56.

通过限制第一行和第一列，可以生成4*3*2=288个矩阵，并检查其中56个是拉丁正方形。然而，我将跳过这一点，从这里开始他们的列表。

首先我们读取并重新排列数据

reduced <- read.table("http://users.cecs.anu.edu.au/~bdm/data/reduced5.txt", head = FALSE, colClasses = "character")
reduced <- lapply(1:nrow(reduced), function(r) matrix(as.numeric(unlist(strsplit(unlist(reduced[r, ]), ""))) + 1, 5))
length(reduced)
# [1] 56

现在让我们生成所有5个！和4！分别为1、2、3、4、5和1、2，3、4的排列。

library(combinat)
perms5 <- permn(1:5)
perms4 <- permn(1:4)

最后，我们检查了所有缩小的拉丁正方形，并以所有可能的方式排列它们

allLS <- sapply(reduced, function(m) {
LS <- vector("list", gamma(6) * gamma(5))
for(i in 1:gamma(5))
for(j in 1:gamma(6))
LS[[(i - 1) * gamma(6) + j]] <- m[perms4[[i]] + 1, perms5[[j]]]
LS
})

只需要几秒钟，我们就可以得到的结果

length(allLS)
# [1] 161280

很容易验证它们是否都是不同的

table(table(sapply(allLS, paste0, collapse = "")))
#      1 
# 161280 

你也可以检查一下它们是否都是拉丁方块。