How to generate a random matrix without repeating across rows and columns?
This algorithm will do the trick, assuming you want to contain all elements between 1
andn
%// Elements to be contained, but no zero allowed
a = [1 2 3 4];
%// all possible permutations and its size
n = numel(a);
%// initialization
output = zeros(1,n);
ii = 1;
while ii <= n;
%// random permuation of input vector
b = a(randperm(n));
%// concatenate with already found values
temp = [output; b];
%// check if the row chosen in this iteration already exists
if ~any( arrayfun(@(x) numel(unique(temp(:,x))) < ii+1, 1:n) )
%// if not, append
output = temp;
%// increase counter
ii = ii+1;
end
end
output = output(2:end,:) %// delete first row with zeros
This will definitely not be the fastest implementation. I would be curious to see others. The computation time increases exponentially. But everything up to 7x7 is tolerable.
source to share
A way to approach this problem is to create a circular matrix and shuffle it.
mat_size = 4
A = gallery('circul', 1:mat_size); % circular matrix
B = A( randperm(length(A)) , randperm(length(A)) ); % shuffle rows and columns with randperm
He gives
A =
1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1
B =
3 4 1 2
2 3 4 1
4 1 2 3
1 2 3 4
This method should be fast. The size 11 problem computes in 0.047021 seconds.
source to share
I wrote some more code (interesting to compare timings and make it parallel if possible). Also there was a problem with perms
(need to restart Matlab to be able to generate for 11 elements, I have x64 and 16GB of memory). Then I decided to save symbols instead of numbers, reducing the memory occupied by the matrix. This, of course, generates all the permutations, and I first shuffle them, picking a new random order in the loop. It works faster and eats up less memory. The time for 11 x 11 (differs from run to run of course) is shown in the results.
clear all; t = cputime; sze = 11; variations = perms(char(1 : sze)); % permutations varN = length(variations); variations = variations(randperm(varN)', :); % shuffle sudoku = zeros(sze, sze); sudoku(1, :) = variations(1, :); % set the first row indx = 2; for ii = 2 : varN % take a random index rowVal = variations(ii, :); % check that row numbers do not present in table at % corresponding columns if (~isempty(find(repmat(rowVal, sze, 1) - sudoku == 0, 1))) continue; end; sudoku(indx, :) = rowVal; disp(['Found row ' num2str(indx)]); indx = indx + 1; if indx > sze, break; end; end; disp(cputime - t); disp(sudoku);
Result
252.9712 seconds
7 11 3 9 6 2 4 1 8 10 5
1 9 6 3 10 7 11 5 2 4 8
9 6 11 8 2 10 1 7 4 5 3
4 10 7 11 1 8 5 2 6 3 9
2 5 9 1 3 6 8 4 10 7 11
10 3 5 6 7 4 2 9 11 8 1
6 4 2 10 8 5 3 11 9 1 7
3 8 10 4 11 1 7 6 5 9 2
11 1 8 5 4 9 6 3 7 2 10
5 2 4 7 9 3 10 8 1 11 6
8 7 1 2 5 11 9 10 3 6 4
source to share
Here's a memory-efficient approach. The time it takes is random, but not very long. All possible output matrices are equally likely.
This works by randomly filling the matrix until no more positions are available or until the entire matrix is filled. The code is commented, so it should be obvious how it works.
For size 11, this takes on the order of a few thousand or tens of thousands of attempts. On my old laptop, this means (random) runtime from a few seconds to tens of seconds.
It could be sped up by using uint8
values instead of double
. I don’t think it’s a big win.
Code:
clear all
n = 11; %// matrix size
[ ii jj ] = ndgrid(1:n); %// rows and columns of S
ii = ii(:);
jj = jj(:);
success = 0; %// ...for now
attempt = 0; %// attempt count (not really needed)
while ~success
attempt = attempt + 1;
S = NaN(n, n); %// initiallize result. NaN means position not filled yet
t = 1; %// number t is being placed within S ...
u = 1; %// ... for the u-th time
mask = true(1, numel(ii)); %// initiallize mask of available positions
while any(mask) %// while there are available positions
available = find(mask); %// find available positions
r = randi(numel(available), 1); %// pick one available position
itu = ii(available(r)); %// row of t, u-th time
jtu = jj(available(r)); %// col of t, u-th time
S(itu, jtu) = t; %// store t at that position
remove = (ii==itu) | (jj==jtu);
mask(remove) = false; %// update mask of positions available for t
u = u+1; %// next u
if u > n %// we are done with number t
t = t+1; %// let go with new t
u = 1; %// initiallize u
mask = isnan(S(:)); %// initiallize mask for this t
end
if t > n %// we are done with all numbers
success = 1; %// exit outer loop (inner will be exited too)
end
end
end
disp(attempt) %// display number of attempts
disp(S) %// show result
Result example:
10 11 8 9 7 2 3 4 1 6 5
8 4 2 1 10 11 6 5 7 9 3
2 3 5 6 11 8 1 10 4 7 9
9 8 7 4 6 10 11 3 5 1 2
3 5 9 8 2 1 4 7 6 11 10
11 9 4 5 3 6 2 1 8 10 7
1 2 6 3 8 7 5 9 10 4 11
7 1 11 10 5 4 9 8 2 3 6
4 7 1 2 9 3 10 6 11 5 8
6 10 3 11 1 5 7 2 9 8 4
5 6 10 7 4 9 8 11 3 2 1
source to share