Permutations with repeated measures Let's say I have data from several mice with id id. Each mouse wandered around two mazes (A and B) and I gave a score at the end of the run (score).

dat <- data.frame(id=c(1, 1, 2, 2, 3, 3, 4, 4), maze=c("A", "B", "A", 
        "B", "A", "B", "A", "B"), score=c(10, 21, 13, 9, 12, 16, 3, 
        18))

      id maze score
    1  1    A    10
    2  1    B    21
    3  2    A    13
    4  2    B     9
    5  3    A    12
    6  3    B    16
    7  4    A     3
    8  4    B    18

I'd like to do a permutation test to test the difference between maze A and maze B.
Am I allowed to completely shuffle the scores:
    id  maze  score
    1    A     21
    1    B     3
    2    A     18
    2    B     10
    3    A     13
    3    B     9
    4    A     16
    4    B     12

or do I need to shuffle within maze (shuffle the A scores with A scores, and B scores with B scores):
    id  maze  score
    1    A     3
    1    B     9
    2    A     10
    2    B     16
    3    A     12
    3    B     21
    4    A     13
    4    B     18


Some mice will tend towards high scores, some mice will tend towards low scores independent of the Null you are investigating. As this is independend of our Null, we do not want to permute that. Mice with generally large scores can stay mice with large scores. Mice with two simlar scores in both mazes can stay mice with similar scores.
In the end you want to compute a difference of maze A and maze B scores per mouse and compare that to the permutation distribution. To investigate the relevance of maze, the assignment of any score to the maze is what needs to be permuted whilst keeping everything else the same.
For each mouse, we need to either relabel the maze B score as maze A score AND the maze A score as maze B score or not relabel anything. If the Null holds, that should be no problem.
This should insure not to destroy the absolute within-mouse differences but only permute the assignment of each pair of measurements to a maze.
In the end, we are interested in computing the $A - B$ value. When the assignment of the values to A and B are switched, that will be the same as multiplying the value to -1.
$A - B = -B + A = -1\times(B - A)$
So the easiest way computationally will be to once compute the difference A minus B and then randomly either multiply that by -1 or not.
dat <- data.frame(id=c(1, 1, 2, 2, 3, 3, 4, 4), 
                  maze=c("A", "B", "A", "B", "A", "B", "A", "B"), 
                  score=c(10, 21, 13, 9, 12, 16, 3, 18))

# convert that to a wide format

dat.wide <- merge(x = subset(dat, maze == "A"), y = subset(dat, maze == "B"),
                  by = "id")
print(dat.wide)

# compute differences

diff <- dat.wide$score.x - dat.wide$score.y  # these are the differences without permuting

# multiply any difference by -1 or 1 a large number of times

diffs <- replicate(1e5, {sample(c(-1, 1), length(diff), TRUE) * diff})

#plot cumulative density function of diffs to compare to the truely observed difference
plot(ecdf(colSums(diffs)), 
     xlab = "sums of (permuted) differences in maze scores",
     ylab = "cummulative share",
     main = "")
abline(v = sum(diff), col = "red")
text(x = sum(diff), y = .8, labels = "true observation", col ="red")
axis(3, sum(diff), col.ticks = "red", col = "red")
axis(4, c(.025, .975), col = "red", labels = c("2.5%", "97.5%") )


(with 4 values we expect 16 possible permutations so there should be 15 change points  in this graph. However, in the given example, one true difference is 4 and one is -4, therefore there are less points in the graph)
