Passing through each element in a matrix just once and randomly

Hello everyone, I have a very big nxn matrix which I want to visit element-per-element randomly, without repetition, i.e. first the A(4,100) term, then the A(53,20) term, and so on. I'm not saying I want the value of each element to be random, I want the order in which each element is visited to be random, and if possible to go through each element just once, due to the vastness of the matrix (2500x2500). I'm thinking the way to go is in the posible permutations between two 1-to-2500 groups of elements. But I'm not completely sure about that approach. Any help will be highly appreciated, Carlos

Answer 1

[Roger Stafford]

   B = A(randperm(prod(size(A))));

The vector B will have each value of A once and only once in random order.

[Carlos]

Totally did it, thanks a lot.

[Jos (10584)]

numel(A) can replace prod(size(A))

Answer 2

[Image Analyst]

Carlos:

If you want "I want the order in which each element is visited" and "the way to go" then I would get the indexes of that route, path, sequence of indexes, or whatever you want to call it, like this:

linearIndexes = randperm(numel(A));  % All indexes scrambled up.

This gives the indexes to visit. If you want the values at those indexes, then you can use Roger's method, which is essentially

randomValues = A(linearIndexes);

Answer 3

[John BG]

With Stafford's answer, there is a chance you do not get certain combinations and repeat some others, if it's an image, certain pixels, while you may repeat other pixels.

The exhaustive way is to randomly choose one by one, but while avoiding repetition, go through all possible combinations.

for that purpose:

P=combinations(1:2500,1:2500);
L=randperm(length(P));   % L is 6250000
for k=L
   A(k,:)
   % process here
end

If you find this answer of any help solving your question,

please click on the thumbs-up vote link, thanks in advance

John

[e-mail]

[Roger Stafford]

"With Stafford's answer, there is a chance you do not get certain values, certain pixels, while you may repeat other pixels."

I thoroughly disagree, John! There is no such chance! The number prod(size(A)) is the total number of elements in matrix A, and hence randperm(prod(size(A))) generates a random permutation of all the numbers from 1 to numel(A) (which I could have used.) Each is a linear index into A and each appears once and only once. That is the nature of permutations. Therefore no value is left out, and no value is repeated. The only alteration is in the order.

[Image Analyst]

I agree with Roger, and is almost what I would have said myself. I think John read too quickly and thoguht he used randi() instead of randperm(). See my answer for what I say.

[John BG]

With Stafford answer there is a small possibility that with randperm, (not randi) you get same shuffle, because your are not shuffling the numeral referring to all possible combinations, but the bucket stack you pull cards from.

randperm shuffles the stack, more or less randomly, so you may get twice same combination, while missing certain combinations, if not shuffling enough times. And the more times you shuffle, attempting to avoid missing any possible combination, the higher the possibility you repeat a combination.

Yet with a single shuffle of the numerals of all possible permutations, and then reading that single shuffle of pointers, you can neither miss any pixel combination nor hit twice same pixel combination.

Carlos is clear on this point: he wants to read ALL pixels, each once only, randomly.

Why do you think that shuffling the stack you are going to get exactly once each pixel combination, but you are not going to repeat ANY pixel combination at all?

Image Analyst seems to agree, it's the indices of all permutations what you have to shuffle.

You really need to get this right, because if you tell your students that it would work to for instance encrypt/decrypt an image, you are losing/adding noise in a process that should be transparent.

Hope it's clear if not just let me know and I will kindly add more examples.

John

[e-mail]

[Jos (10584)]

Carlos wrote: "I want the order in which each element is visited to be random, and if possible to go through each element just once"

VeryBixMatrix = 10*[1 2 3; 4 5 6] % ;-)
Nelements = numel(VeryBixMatrix)
IndexVisitOrder = randperm(Nelements)
for k=1:Nelements,
   CurrentIndex = IndexVisitOrder(k)
   CurrentElement = VeryBixMatrix(CurrentIndex)
end

[John BG]

Jos, if some asks 'I want this, and that, and if possible blue_yonder', the implicit question usually means 'I want this that blu_yonder'.

The question 'if possible' clearly implies 'I don't know how to .. but if you know and want to show me .. kindly appreciated'.

You don't want the uncertainty of guessing whether all pixels will be hit at least once, or repeated or missing, do you?

And right on the top of the question, the sentence again is clear:

 ' want to visit element-per-element randomly, without repetition'

when facing contradictory statements, one requesting certainty and another one kind of 'if possible'.. any one wishing to answer the question correctly goes for the random shuffle of the numerals of all possible permutations.

[John BG]

'element-per-element'

in French, Spanish, Portuguese and Italian exactly same preposition: one by one - all of them - once.

In English 'per' is also accepted, the Normans brought it along 'per capita' 'percent' 'per calendar month'.

who wants to pay rent twice on January, and reach March guessing whether February is going to be colected?

Common sense, think logically.

[Roger Stafford]

To John: You speak of the "small possibility of getting the same shuffle". However, in so doing you seriously misinterpret Carlos' request, in my opinion. He says nothing about a repeated visit with a repeated "shuffle". He wants a single random ordering of the elements in his vector, and if he happens to by chance get the same order as he already had, that is presumably all right - it is one of the possible permutations. (Of course, with 6,250,000-factorial possible permutations the chance of that is mighty small.) Note carefully what the word 'permutation' means, John. It means that each quantity in the original list occurs again in the permuted ordering of that list just once and only once - no repetitions, no omissions.

In any case, this is what Matlab's 'randperm' function does, and I believe it does a very satisfactory job. I have observed the logic behind the 'randperm' operation. For "randperm(N)" it computes N successive random values, each ranging from zero to one using the 'rand' function, and then it sorts these values. It uses the permutation that is involved in that sorting as its output. If you assume that the 'rand' function is doing its job properly, and that 'sort' doesn't lose track of some of its values, this means that the result is a valid permutation and each of the N-factorial possible permutations is equally likely. I believe that is all Carlos is asking. If you doubt that, I suggest you direct your question to him directly.

[John BG]

agreed, we here locking horns and the originator saying nothing.

All the best

John

[e-mail]