Select random numbers from matrix without repetition

I have a matrix C11 of dimension 1024*1024 .

How can I get 4 sub matrices (of dimension 64*16) from C11 without the repetetion of elements from other matrices? That is 4 distinct submatrices with random elements from C11. I have tried something like this but it is not executing well and making no sense logically.

   c=0;
while i==randperm(4,1)
   c=c+1;
    if c~=4
        switch i
            case 1
                cluster1= c11(randperm(size(c11,1),64),i:(i-1)+16);
            case 2
                cluster2= c11(randperm(size(c11,1),64),i:(i-1)+16);
            case 3
                cluster3= c11(randperm(size(c11,1),64),i:(i-1)+16);
            case 4
                cluster4= c11(randperm(size(c11,1),64),i:(i-1)+16);         
             
        end
    
    end
end 

[Rik]

You should try to make a list of indices. With every randomly generated index (see randi) you can check if it overlaps with any of the other samples.

[Sam]

Okay. Got it. Let me get back after trying. Thank you..

[J. Alex Lee]

it seems sticking with randperm will avoid needing to check for overlaps

for clarification, are you looking for random contiguous 64x16 blocks from the 1024x1024 matrix, or just any random 1024 non-overlapping elements rearranged into a 64x16 block?

[Sam]

I am looking for random 1024 non-overlapping elements rearranged into 64*16 blocks (with out repetetion of elements from previous blocks)

Thanks for asking. It made my question more explicit.

[J. Alex Lee]

Hmm, based on your reply, it would seem my short answer for "not contiguous blocks" is what you are looking for...well in any case glad you found an answer that works for you.

Answer 1

[Image Analyst]

Sam, try this. It gets potential candidate locations at random, then checks to see if a rectangle at that location would overlap with any of the prior rectangles. If it doesn't, then it's added to the "keeper" list. If there is an overlap it keeps trying again until all 4 rectangles have been placed. Adapt as needed.

clc;    % Clear the command window.
clear all;
close all;
workspace;  % Make sure the workspace panel is showing.
format short g;
format compact;
fontSize = 15;
fprintf('Beginning to run %s.m ...\n', mfilename);

% I have a matrix C11 of dimension 1024*1024 .
C11 = randi(9, 1024, 1024);
[rows, columns] = size(C11)
% Create matrices to hold the final locations we decided upon.
chosenRows = -64 * ones(1, 4);
chosenColumns = 16 * ones(1, 4);
% How can I get 4 sub matrices (of dimension 64*16) from C11
matrixCounter = 0;
loopCounter = 1;
maxIterations = 1000; % Fail safe in case can't find enough so we don't get into an infinite loop.
while matrixCounter < 4 && loopCounter < maxIterations
	potentialRow = randi(rows - 63, 1);
	potentialCol = randi(columns - 15, 1);
	if matrixCounter == 0
		% Can always take the first selection of course.
		chosenRows(matrixCounter + 1) = potentialRow;
		chosenColumns(matrixCounter + 1) = potentialRow;
		matrixCounter = matrixCounter + 1;
	else
		% See if this location overlaps any prior locations.
		noRowOverlap = true(1, matrixCounter); % Initialize to correct length.
		noColOverlap = true(1, matrixCounter); % Initialize to correct length.
		for k = 1 : matrixCounter
			noRowOverlap(k) = (potentialRow <= chosenRows(k) - 64) || (potentialRow >= chosenRows(k) + 64);
			noColOverlap(k) = (potentialCol <= chosenColumns(k) - 16) || (potentialCol >= chosenColumns(k) + 16);
		end
		if all(noRowOverlap) && all(noColOverlap)
			% No overlap so we can add this location on to our list.
			chosenRows(matrixCounter + 1) = potentialRow;
			chosenColumns(matrixCounter + 1) = potentialCol;
			matrixCounter = matrixCounter + 1;
		end
	end
	loopCounter = loopCounter + 1;
end
% Display them
rectangle('Position', [0, 0, 1024, 1024], 'EdgeColor', 'b', 'LineWidth', 2); % Outer, whole matrix.
hold on;
for k = 1 : size(chosenRows, 2)
	% Display the individual rectangles.
	rectangle('Position', [chosenRows(k), chosenColumns(k), 16, 64], 'EdgeColor', 'r', 'LineWidth', 2);
end
fprintf('Done running %s.m.\n', mfilename);

[Sam]

Thank you!...Got it.

Answer 2

[J. Alex Lee]

Here is a simple way if you don't need contiguous blocks, but just need to randomly sample elements without repeating

L = 1024;  % size of square parent matrix
M = 64;    % number of rows of sub matrices
N = 16;    % number of cols of sub matrices

s = 4;     % number of sub matrices

C = rand(L,L);

% choose non-overlapping indices of all sub matrices
AllIdx = randperm(L*L,M*N*s);

% reshape indices into matrix for easier looping
idx = reshape(AllIdx,s,M*N);

for i = s:-1:1
	sub{i} = reshape(C(idx(i,:)),M,N);
end

[Sam]

Thank you.... Understood both the approaches. Let me check the other way I tried..

Answer 3

[J. Alex Lee]

And here is a different approach to the contiguous blocks. Instead of checking for overlaps, you can avoid them by tagging elements of the matrix you do not want to sample randomly from. This strategy might be better suited if you need to sample a lot of blocks...admittedly, trial and error should work pretty well for only 4 small blocks in a pretty big matrix...but if you have many large blocks, you don't want to waste a lot of loops if there's no more possible blocks to choose.

clc;
close all;
clear;

% original problem size
szSRC = [1024,1024]; % size of square source matrix
szSUB = [64,16];     % size of sub matrices
nSub = 40;           % number of sub matrices

% test problem size
szSRC = [13,15]; % size of square source matrix
szSUB = [5,4];  % size of sub matrices
nSub = 50;      % number of sub matrices

% create a random source matrix
SRC = randi(9,szSRC);

% reduce the problem to selecting upper right corners (URC) of sub matrices
% from the source matrix. This immediately eliminates from the choice
% strips on the right and bottom of the source matrix:
% - a horizontal strip on the bottom of height szSUB(1) - 1
% - a vertical strip on the right of width szSUB(2) - 1

% So the size of a "Selection" matrix from which URCs can be chosen is
szSEL = szSRC - (szSUB - 1);

% The list of all linear indices into this "Selection" matrix is
idxALL = (1:prod(szSEL))';

% every valid URC sets an out-of-bounds (OOB) mask for subsequent choices
% it is a rectangle of size szSUB, extended left and up by (szSUB - 1)
% thus, the meshgrid of the OOB masks's rows and columns
% relative to the URC have dimensions 2*szSUB-1 and are symmetrical about
% the center-lines where the offset from the URC is 0:
szOOBh = szSUB-1;
subOOB_0{1} = (-szOOBh(1):szOOBh(1))' + zeros(1,2*szOOBh(2)+1); % rows
subOOB_0{2} = (-szOOBh(2):szOOBh(2))  + zeros(2*szOOBh(1)+1,1); % cols

% initialize the out-of-bounds linear indices, held in a cell array
idxOOBList = cell(nSub,1);

% for visualization only / can comment below
[SrcCols,SrcRows] = meshgrid(1:szSRC(2),1:szSRC(1));
colrs = lines(nSub);
figure; cla; hold on;
set(gca,'XLim',[1,szSRC(2)],'YLim',[1,szSRC(1)],'YDir','reverse');
% end for visualization / can comment above

for c = nSub:-1:1
	
	% the list of available indices to choose next URC from
	% elements of the selection matrix that aren't out-of-bounds is
	idxAVL = setdiff(idxALL,vertcat(idxOOBList{:}));
	
	% check if there are any more possible choices for URC
	if isempty(idxAVL)
		fprintf('No more available choices!\n')
		break
	end
	
	% choose the URC of new sub matrix randomly from idxAVL
	idxURC = idxAVL(randi(numel(idxAVL)));
	
	% find subscripts corresponding to the linear index
	% must use the selection matrix size for conversion
	% but note that the subscripts are applicable to both the source matrix
	% and the selection matrix
	[subURC(1),subURC(2)] = ind2sub(szSEL,idxURC);
	
	% loop along each dimension to...
	for d = 2:-1:1
		
		% ...find the span of subscripts in the sub matrix
		subSUB{d} = subURC(d) + (0:(szSUB(d)-1));
		
		% ..find all the subscripts in the OOB mask
		subOOB{d} = subURC(d) + subOOB_0{d};
		
	end
	
	% convert the OOB subscripts into linear indices
	% and store it in the OOB list to avoid in subsequent sampling
	idxOOBList{c,1} = sub2ind2_nochk(szSEL,subOOB{:});
	
	% extract the sub matrix from the source matrix
	submatrices{c,1} = SRC(subSUB{:});
	
	% for visualization only; can comment the rest of this loop
	idxChk = sub2ind2_nochk(szSRC,subOOB{:});
	plot(SrcCols(idxChk),SrcRows(idxChk),'xk')
	plot(SrcCols(subSUB{:}),SrcRows(subSUB{:}),'o','Color',colrs(c,:))
	drawnow
	
end

% clean up unused cells
submatrices(cellfun('isempty',submatrices)) = [];

% report
fprintf("found %d/%d random blocks before running out of moves\n",numel(submatrices),nSub)

function ndx = sub2ind2_nochk(sz,idx,jdx)
% no check sub2ind specific to 2D
% i and j may be supplied as matrices of same size
subs = [idx(:),jdx(:)];
mask = any([subs<1,subs>sz],2);
ndx = idx(~mask) + (jdx(~mask)-1)*sz(1);
end