如何在 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

基本上，您要求所有 row/column 排列。对于 n x n 矩阵，有 n! (n 阶乘) 排列的行和 n!列的排列，总共 (n!)^2 row/column 个排列（不一定都是唯一的）。

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

# 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

您可以计算 row/column 顺序的所有配对，您可以使用它来获取所有可能的 row/column 排列：

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

Answer 2

基本上你想要的是多重集的排列。包 iterpc 将完成这项工作。

> library(iterpc)
> I <- iterpc(c(3,7), ordered=TRUE)
> getlength(I)
[1] 120
> getall(I)
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
  [1,]    1    1    1    2    2    2    2    2    2     2
  [2,]    1    1    2    1    2    2    2    2    2     2
  [3,]    1    1    2    2    1    2    2    2    2     2
  [4,]    1    1    2    2    2    1    2    2    2     2
  [5,]    1    1    2    2    2    2    1    2    2     2
  [6,]    1    1    2    2    2    2    2    1    2     2
  [7,]    1    1    2    2    2    2    2    2    1     2
  [8,]    1    1    2    2    2    2    2    2    2     1
  [9,]    1    2    1    1    2    2    2    2    2     2
 [10,]    1    2    1    2    1    2    2    2    2     2
 [11,]    1    2    1    2    2    1    2    2    2     2
 [12,]    1    2    1    2    2    2    1    2    2     2
 [13,]    1    2    1    2    2    2    2    1    2     2
 [14,]    1    2    1    2    2    2    2    2    1     2
 [15,]    1    2    1    2    2    2    2    2    2     1
 [16,]    1    2    2    1    1    2    2    2    2     2
 [17,]    1    2    2    1    2    1    2    2    2     2
 [18,]    1    2    2    1    2    2    1    2    2     2
 [19,]    1    2    2    1    2    2    2    1    2     2
 [20,]    1    2    2    1    2    2    2    2    1     2
 [ reached getOption("max.print") -- omitted 100 rows ]

此处每一行都是 1 和 2 的排列。您应该将 1 替换为 -2。

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

How to find all the possible permutations of a matrix in R?

algorithm

r

permutation

matrix