How to randomly shuffle neighbouring elements in a matrix ?

Hi ! I have an array like:

A = [ a b c
      d e f
      g h i ]

How can I randomly shuffle the elements within the array so that neighboring elements (also diagonal) have a higer probability to be shuffled between each others ?

The result I would like to get is something like, but of course at every iteration it would be different.

  A = [ b a c
        g h e
        d f i ]

Hope my question is clear. Thanky for your help

[KALYAN ACHARJYA]

have a higer probability to be shuffled between each others ?

???

[John D'Errico]

When you ask a vague question, with statements like "have a higher probability" then expect to get confused responses.

1 is a higher probabiltiy than 0. Is that sufficient?

You need to define which elements can get swapped with which others. Is this always a 3x3 matrix? And you need to define what you mean by higher, and how you wouldquantify that.

[Alberto Scarampi del Cairo]

True, sorry for the confusion.

I would like that an element is shuffled with a neighboring one twice as much than with any other element in the matrix.

The matrix is now 3x3 but I would like to make it modular so I could change it in the future.

[Image Analyst]

What is an iteration?

In the meantime, you can get a shuffling order with randperm().

[Alberto Scarampi del Cairo]

This function is inside a for loop and I would like to have a different shuffled matrix at evey iteration of the loop.

How can I specify tho shuffle neighboring elements with randperm()?

[Image Analyst]

So for iteration 1 do you shuffle the whole A, or do you just shuffle neighbors of a? Then for the second iteration, do you shuffle the whole A again, or do you shuffle just the neighbors of the value in the location of the original "b" (in other workds, shuffle neighbors of the (2,1) element which would be the 5 neighboring elements at (1,1), (1,2), (2,2), (3,1) and (3,2)?

Give an example of what A might look like after iteration 1, and iteration 2.

[Alberto Scarampi del Cairo]

At every iteration I shuffle the whole A.

For example A matrix at iteration: i = 0:

A = [ a b c
      d e f
      g h i ]

Then at i = 1, I would call the "shuffle" function

  A = shuffle(A)

Which would return the shuffled matrix

  A = [ b a c
        g i f
        d h e ]

Then at i = 2, I would call the "shuffle" again, returning:

A =   [ g a e
        b i f
        h d c ]

Et cetera...

So essentially it is a random shuffle of the elements in a matrix but I do not know how to make it so that neighboring elements are shuffled between each other with a probability that is 2 times the probability of being shuffled with any other elements of the matrix

Answer 1

[John D'Errico]

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?

https://en.wikipedia.org/wiki/Derangement

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.

perms('abcd')
ans =
  24×4 char array
    'dcba'
    'dcab'
    'dbca'
    'dbac'
    'dacb'
    'dabc'
    'cdba'
    'cdab'
    'cbda'
    'cbad'
    'cadb'
    'cabd'
    'bdca'
    'bdac'
    'bcda'
    'bcad'
    'badc'
    'bacd'
    'adcb'
    'adbc'
    'acdb'
    'acbd'
    'abdc'
    'abcd'

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

factorial(9)
ans =
      362880

possible events. That is not too large. However, a4x4 matrix would not be possible to define the entire sample space, since

factorial(16)
ans =
   2.0923e+13

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.