Random matrix with no repeats in rows and columns.

So I have generated a random matrix with dimensions 10x15 with values between 2 and 18 with step length 2.

Simple code:

candidates = 2:2:18;
idx = randi(numel(candidates), 10, 15);
M = candidates(idx)

So my questions is how do I do to never get a value above, under or next to the same value. As the ones I have marked with red in the picture.

[dpb]

I'd guess it not possible with so few candidates in such a large array comparatively -- altho I didn't try to prove that.

You've missed a lot of other locations with the same problem besides those you've marked.

[the cyclist]

It's possible. For example, this "checkerboard" satisfies the criteria:

2*mod((1:15)+(1:10)',2)+ 2

ans = 10×15

2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4

[Francisco Boudagh]

@dpb, I know there are many more locations in the picture but I just marked some of them to show you what I mean.

@the cyclist, I see, but I want all the candidates from 2 to 18, not only 2 and 4 :/

[Jan]

@Francisco Boudagh: So there are much more matrices, but cyclist's solution is one of the valid possibilities, isn't it?

[the cyclist]

@Francisco Boudagh, I was just giving a single counter-example to dpb's concern that a valid solution might not even exist. I was not trying to solve your question.

Answer 1

[Jan]

Create the matrix elementwise. Choose a random element from the available elements. Exclude elements on top and left of the element to be set:

nx   = 15;
ny   = 10;
pool = 1:9;  % Choose values 1:9, multiply by 2 finally
M    = zeros(ny, nx);
for ix = 1:nx
   for iy = 1:ny
       % Exclude elements on the left and on the top from pool:
       exclude = [M(gt0(iy - 1), ix), M(iy, gt0(ix - 1))];
       choose  = pool;
       choose(exclude) = [];
       
       % Nicer but slower in one line:
       % choose = setdiff(pool, [M(gt0(iy - 1), ix), M(iy, gt0(ix - 1))]);
       
       % Choose a random element from the remaining list:
       M(iy, ix) = choose(randi(numel(choose)));
   end
end
M = M * 2

ans = 10×15

6 16 14 8 14 16 14 18 14 6 8 16 18 10 18 18 10 18 4 6 4 18 10 6 4 12 6 8 14 6 2 4 14 18 16 6 16 8 4 10 18 12 14 8 16 4 6 12 8 2 10 6 18 6 14 8 6 18 16 12 8 12 4 2 18 16 10 14 2 10 2 10 6 2 14 10 14 18 14 2 4 16 4 10 6 12 6 12 14 6 8 10 12 2 8 6 12 18 14 18 6 18 8 4 18 14 18 8 6 2 8 14 2 8 6 14 16 18 12 6 16 14 18 12 18 4 2 12 10 18 6 12 16 10 12 6 8 16 6 8 18 12 8 4 8 16 6 18 6 8

function k = gt0(k)
% Reply [] as index, if it is <= 0
if k <= 0, k = []; end
end

I've experimented with cumsum(cumsum(randi([1, 9], 10, 15), 1), 2): There are no repetitions. Then limit the values by rem(). This was not successful. In one dimension it is working, but not in 2.

[Image Analyst]

6 and 8 are repeated in column 1, and 14 is repeated in columns 2 and 3. Lots of other repeats too. he said he wanted no repeats in rows or columns: "no repeats in rows and columns". That's why I suggested a Latin Square which will have no number repeated in either rows or column.

Of course rand() could do that but from teh example it looks like integers are wanted, not fractional numbers.

[Jan]

@Image Analyst: The OP marked neighboring repetitions only in the example. The example given by the cyclist in the comments contains repeated values also, but not as direct neighbors. Therefore I've asked the OP, if his example is a valid output, but this has not been clarified yet.

[Francisco Boudagh]

@Jan

Thank you Jan. That was exactly what I was looking for.

[Image Analyst]

Ok you're right Jan, though it was not clear as you say. @Francisco Boudagh if you want Latin Square code, which won't even have any repeats at all, neighboring or separated, then let me know. I have some code to construct a Latin Square in Visual Basic and could probably translate it into MATLAB fairly easily.

[Francisco Boudagh]

@Image Analyst. Yes please, you can send me latin square code :-)

[Image Analyst]

Latin Squares are a very important concept in the "Design of Experiments" (DOX).

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

Actually there is Latin Square code in the File Exchange:

https://www.mathworks.com/matlabcentral/fileexchange/12315-latsq-n

Answer 2

[the cyclist]

I believe this does what you want.

% Set the random number seed, for reproducibility
rng default

% The pool of random numbers to choose from
pool = 2:2:18;

% The size of the array
M = 10;
N = 15;

% Preallocate the output array
out = zeros(M,N);

% Fill the upper-left element from the pool
out(1,1) = randsample(pool,1);

% Fill the first column, never repeating the just-above value
for i1 = 2:M
    out(i1,1) = randsample(setxor(pool,out(i1-1,1)),1);
end

% Fill the first row, never repeating the just-left value
for j1 = 2:N
    out(1,j1) = randsample(setxor(pool,out(1,j1-1)),1);
end

% Fill the rest of the array, never repeating the just-above and just-left values
for ii = 2:M
for jj = 2:N
    out(ii,jj) = randsample(setxor(pool,[out(ii-1,jj),out(ii,jj-1)]),1);
end
end

out

out = 10×15

16 12 16 12 14 12 14 6 2 14 18 8 16 4 10 4 14 4 14 2 18 10 16 10 18 10 4 14 16 18 14 4 12 6 14 16 14 6 2 10 18 10 2 6 8 6 8 4 14 8 4 6 12 4 2 4 16 4 8 10 18 4 6 18 10 16 8 6 8 6 10 18 10 6 8 4 16 4 2 18 10 4 16 2 14 12 8 16 12 6 18 12 18 10 8 12 16 12 16 6 18 12 4 10 16 14 4 6 8 10 18 8 4 12 14 4 8 10 2 14 8 18 10 4 18 10 12 14 6 2 18 2 8 4 2 16 8 16 18 12 2 10 18 12 16 4 18 10 18 10

I would caution you, though, that I have not thought carefully about the random properties of this array. (For example, does each element have equal probability for each value, etc., that might be important to you.) I think it's probably OK.

Also, if you do not have the Statistics and Machine Learning Toolbox, you will not have the randsample function, and therefore will need to replicate that function's behavior.

[the cyclist]

Just realized that this is effectively the same algorithm as @Jan's.

[Jan]

@the cyclist: If we suggest equivalent algorithm, is it polite or vain, when I consider this as reason to vote for your answer? I cannot solve the emotional dilemma. Luckily this problem has no relation to Matlab and need not be discussed. +1. :-)

I've avoided randsample, because the OP might not have the Statitics Toolbox.

[the cyclist]

:-)

Answer 3

[Image Analyst]

Just construct a Latin square for n=9, then multiply it by 2

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