r - 如何在 R 中找到矩阵的所有可能排列？

Question

我有一个矩阵，例如 5x5。

     [,1] [,2] [,3] [,4] [,5]
[1,]   22   -2   -2   -2    2
[2,]   -2   22    2    2    2
[3,]   -2    2   22    2    2
[4,]   -2    2    2   22    2
[5,]    2    2    2    2   22.

如您所见，矩阵是对称的。在主对角线上方，有4+3+2+1=10个位置，我通过combn找到所有可能的(排列)矩阵，在这10个位置有(-2)3次.这意味着 10!/3!*7!=120 个矩阵。

但其中一些是等价的。

所以，我的问题是如何从 120 中找到非等价矩阵。

我正在考虑置换矩阵，因为如果我从 120 个矩阵中选择一个并使用 rmperm，结果我将得到 120 个矩阵中的一个(随机)。

当我有 5x5 和 6x6 矩阵时，我没有问题，因为我已经开发了一种算法。但是现在我想在 7x7 矩阵和更多矩阵中做同样的事情，但是算法非常慢，因为我有很多循环。

所以，当我从 120 个矩阵中选择一个矩阵时，我想用一个命令给我 120 个矩阵中的所有排列矩阵。

非常感谢!

Answer 1

基本上，您要求所有行/列排列。对于 n x n 矩阵，有 n! (n 阶乘) 排列的行和 n!列的排列，总共 (n!)^2 行/列排列(并非所有排列都必须是唯一的)。

第一步是获取样本数据集并获取行/列索引的所有排列的集合(我假设是方矩阵，但很容易扩展到非方矩阵):

# Sample dataset:
library(sna)
set.seed(100)
(g <- rgraph(3))
#      [,1] [,2] [,3]
# [1,]    0    0    1
# [2,]    1    0    0
# [3,]    1    1    0

# All permutations of indices
library(gtools)
(perms <- permutations(nrow(g), nrow(g)))
#      [,1] [,2] [,3]
# [1,]    1    2    3
# [2,]    1    3    2
# [3,]    2    1    3
# [4,]    2    3    1
# [5,]    3    1    2
# [6,]    3    2    1

您可以计算行/列排序的所有配对，您可以使用它来获取所有可能的行/列排列:

pairings <- expand.grid(1:nrow(perms), 1:nrow(perms))
head(pairings)
#   Var1 Var2
# 1    1    1
# 2    2    1
# 3    3    1
# 4    4    1
# 5    5    1
# 6    6    1
all.perms <- lapply(1:nrow(pairings), function(x) g[perms[pairings[x,1],], perms[pairings[x,2],]])
head(all.perms)
# [[1]]
#      [,1] [,2] [,3]
# [1,]    0    0    1
# [2,]    1    0    0
# [3,]    1    1    0
# 
# [[2]]
#      [,1] [,2] [,3]
# [1,]    0    0    1
# [2,]    1    1    0
# [3,]    1    0    0
# ...

最后，您可以使用 unique 来获取作为唯一矩阵的 all.perms 的元素:

all.unique.perms <- unique(perms)
length(all.unique.perms)
# [1] 18