fill matrix randomly with a specific number of units

Hi,

I am trying to generate a matrix that is a specific size and is filled with a specific number of items but placed randomly in columns. For example, I have 4 apples, 3 oranges and 2 grapes. I want a matrix with 3 rows and 9 columns where the apples, oranges and grapes are placed randomly in the row and there are always 4,3 and 2 of the respective fruit in a row. Also, they need to be placed such that the rows are not identical. So I don't want [ a o a a o a o g g; a o a a o a g g; a o a a o a g g]. It is fine, and expected, that some will repeat in the same column.

Thanks in advance, Tom

[Kirby Fears]

Thomas,

You can think of this problem as choosing a random permutation of 9 characters 'aaaaooogg' such that the resulting string is not identical to any prior strings.

There are two typical approaches to this. If your number of rows is small compared to the sample space of permutations you could make a random permutation of 9 characters, check if it matches any previously computed strings, and finally add the new string to your array (or toss it and try again if it's a duplicate). This approach is generally very fast if the number of rows is small compared to the size of the permutation space, but it could be dangerously time consuming if that's not the case.

The other approach is to compute all the permutations of your 9 characters up front, toss out all duplicate strings, and randomly draw from the remaining strings. This approach is more stable, but there will be a high cost of memory and computational time to compute all permutations up front.

Ultimately, you could code both methods and choose one method at runtime based on the desired number of rows relative to the number of possible permutations.

Answer 1

[Roger Stafford]

The tough part of your requirement is to not duplicate rows. The following while-loop is intended to accomplish that.

   v = [4;3;2]; % Numbers of apples, oranges, and grapes, resp.
   r = 100; % <-- Choose the number of rows for the matrix
   u = cumsum([1;v]);
   n = u(end)-1;
   w = cumsum(accumarray(u,1));
   w = w(1:end-1).'; % w = [1,1,1,1,2,2,2,3,3]
   M = zeros(r,n);
   M(1,:) = w(randperm(n)); % Get first row
   for k = 2:r
     b = true;
     while b  % Repeat until next row is unique
       M(k,:) = w(randperm(n)); % Get next row
       b = any(all(M(1:k-1,:)==repmat(M(k,:),k-1,1),2),1);
     end
   end

The matrix 'M' now has indices 1, 2, and 3 which represent apples, oranges, and grapes, respectively.