You can't easily talk about the probability of two specific elements being exchanged, because things are not independent. For example, consider the case of a simple 2x2 matrix.
M = [a b;c d]
Lets suppose that we consider the elements a and b, and a and c are neighboring, but a and d are not so. So neighboring refers only to those elements that are horizontally or vertically adjacent.
Next, in a given "shuffle" MUST all elements move? That is, are your huffles actually derangements?
A derangement is by definition a permutation with no fixed elements. Or may some stay unchanged? I'll asume for this thought exercise that all must move, so we are working with derangements. (Given 4 elements, there are only 3 possible derangements.)
Anyway, if we swap elements a and b, then c and d must also be swapped. Call this event shuffle1.
By way of comparison, I'll create a second shuffle where a and d are swapped. That means C and B must also be swapped. Call this shuffle2.
Is the probability of the shuffle1 event TWICE that of shuffle2? Or, logcally, is the probability of shuffle1 FOUR times as high as shuffle2?
Sadly, I think you have a very difficult problem here, mainly because you NEED to be specific. Until you actually define what you mean by these concepts, nothing makes sense. So you cannot talk about the "probability" specific element moving to some location in isolation. The shuffle that you describe encompasses many moves, and as such, does not seem to make good sense as you describe it in terms of "probability".
Next, for a simple case of a 2x2 matrix, perhaps it would be simplest to just list ALL possible shuffles. For a 2x2 matrix, there are then 24 possible shuffles.
24×4 char array
A simple solution would be to just assign the probability that each of those events can arise from the initial sequance 'abcd'. Imagine that we reshape each of these into a 2x2 array, so all that matters is the string sequence. If you can assign a probability of any of those specific shuffles, then your problem is trivially solved. Since the initial matrix MUST have been 'abcd', and the result of any shuffle is one of those events listed, then the sum of all those probabilities must equal 1.
So just generate a discrete random number using those probabilites. A tool like randsample, found in the stats toolbox, can do the sampling given a set of probabilities you have assigned to each event.
This is simple for the2x2 case, although it forces you to do the assignment of probabilities in advance. But surely you need to do exactly that. However, can yo do this for a larger matrix? Well, I suppose a 3x3 is possible, since the sample space has only
possible events. That is not too large. However, a4x4 matrix would not be possible to define the entire sample space, since
is a relatively huge number. And beyond that point you have no hope at all on any computer that you will see in the near future.
So, can there be a simple scheme to do what you wish, on say even as little as a 5x5 array? That will be very difficult, surely at least until you are willing and able to define what the probability of any transition to any specific shuffle is. Again, you need to be specific, as you cannot write code to do what you cannot even define in mathematical terms.
Perhaps what you need to start with is to define the "distance" between any pair of shuffles. If two shuffles are equally distant from the base nxn matrix, then you will arguably decide they are equally probable events. What "probability" would you assign to that event? Next, consider the next closest shuffle. Again, a lot depends on whether you require complete derangements, or if ANY permutation is valid.