Как найти все возможные перестановки матрицы в 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 все возможные (перестановочные) матрицы, которые имеют (-2) 3 раза в этих 10 положениях. Это означает, что 10!/3! * 7! = 120 матриц.

Но некоторые из них являются эквивалентными.

Итак, моя проблема заключается в том, как найти неэквивалентные матрицы из 120.

Я принимаю около матриц перестановок, потому что если я выбрать один из 120 матриц и я использую rmperm, я как результат один (случайный) из 120 матриц.

Когда у меня есть матрицы 5x5 и 6x6, у меня нет проблем, потому что я разработал алгоритм. Но теперь я хочу сделать то же самое в матрице 7x7 и более, но алгоритм очень медленный, потому что у меня много циклов.

Итак, я хочу с одной командой, когда я выбираю матрицу из 120 матриц, чтобы дать мне все матрицы перестановки из 120.

Спасибо большое!

Answer 1

В принципе, вы хотите переставить мультимножество. Пакет 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.

Answer 2

В принципе, вы запрашиваете все перестановки строк/столбцов. Для 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