# [R] permutations of a binary matrix with fixed margins

Paul Johnson paulj at stats.gla.ac.uk
Tue Oct 2 17:06:44 CEST 2007

```Jérôme,

As a first attempt, how about the function below. It works (or not) by
randomly sorting the rows and columns, then searching the table for
"squares" with the corners = matrix(c(1,0,0,1),ncol=2) and subtracting them
from 1 to give matrix(c(0,1,1,0),ncol=2) (and vice versa). Randomized
matrices can be produced as a chain where each permutation is seeded with
the previous one.

Potential problems:
1. Does it really explore all possible permutations? Does it do it in an
unbiased way?
2. Related to above: there is potential autocorrelation (although I haven't
found it with my data set), so might need some dememorisation steps.
3. It's slow and dememorisation makes it slower.
4. It isn't clear to me whether it needs the added stochastic element, i.e.
squares are only flipped if "runif(1)<0.5". In practice it seems to work
without it (as far as I can tell, i.e. it isn't autocorrelated using my data
set).

I suspect there's a much better way of doing this, which might take the
margins as an input, and therefore wouldn't be directly derived from any
particular matrix structure.

Paul

###############################################################

# function to permute binary matrix keeping margins fixed.
# the input "x" is the binary matrix to be permuted

permute.struct<-
function(x)
{
x<-x[rownames(x)[sample(1:nrow(x))],colnames(x)[sample(1:ncol(x))]]
pattern<-c(1,0,0,1)
for(i in 1:(nrow(x)-1))
for(j in 1:(ncol(x)-1))
for(ii in (i+1):nrow(x))
for(jj in (j+1):ncol(x))
{
query<-c(x[c(i,ii),c(j,jj)])
if((all(query-pattern==0) || all(query==1-pattern)) &&
runif(1)<0.5)
x[c(i,ii),c(j,jj)] <- 1 - x[c(i,ii),c(j,jj)]
}
x
}

###############################################################

--------------------------------------------------------
From: Mathieu Jérôme <jerome.mathieu_at_snv.jussieu.fr>
Date: Thu 05 Apr 2007 - 13:34:01 GMT

Dear R Users,
How can I randomize a matrix (with contains only 0 and 1) with the
constraint that margin totals (columns and rows sums) are kept constant?
Some have called this "swap permutation" or something like that.

The principle is to find bloc of
10
01
and change it for
01
10
there can be several rows or columns between these numbers. It probably
exists in R, but I can't find the function. I am aware of permcont, but it
works only for 2x2 matrices