How to construct a 128x32 scrambled matrix?

Question

How can I construct a scrambled matrix with 128 rows and 32 columns in vb.net or Matlab?

Entries of the matrix are numbers between 1 and 32 with the condition that each row mustn't contain duplicate elements and rows mustn't be duplicates.

Answer 1

This is similar to @thewaywewalk's answer, but makes sure that the matrix has no repeated rows by testing if it does and in that case generating a new matrix:

done = 0;
while ~done
    [~, matrix] = sort(rand(128,32),2);
    %// generate each row as a random permutation, independently of other rows.
    %// This line was inspired by randperm code
    done = size(unique(matrix,'rows'),1) == 128;
    %// in the event that there are repeated rows: generate matrix again 
end

If my computations are correct, the probability that the matrix has repteated rows (and thus has to be generated again) is less than

>> 128*127/factorial(32)
ans =
  6.1779e-032

Hey, it's more likely that a cosmic ray will spoil a given run of the program! So I guess you can safely remove the while loop :-)

Answer 2

With randperm you can generate one row:

row = randperm(32)

if this vector wouldn't be that long you could just use perms to find all permutations:

B = perms(randperm(32))

but it's memory-wise too much! ( 32! = 2.6313e+35 rows )

---

so you can use a little loop:

N = 200;    

A = zeros(N,32);
for ii = 1:N
    A(ii,:) = randperm(32);
end

B = unique(A, 'rows');
B = B(1:128,:);

For my tests it was sufficient to use N = 128 directly and skip the last two lines, because with 2.6313e+35 possibly permutations the probability that you get a correct matrix with the first try is very high. But to be sure that there are no row-duplicates choose a higher number and select the first 128 rows finally. In case the input vector is relatively short and the number of desired rows close to the total number of possible permutations use the proposed perms(randperm( n )).

---

small example for intergers from 1 to 4 and a selection of 10 out of 24 possible permutations:

N = 20;    
A = zeros(N,4);
for ii = 1:N
    A(ii,:) = randperm(4);
end
B = unique(A, 'rows');
B = B(1:10,:);

returns:

B =

     1     2     3     4
     1     2     4     3
     1     3     4     2
     2     3     1     4
     2     3     4     1
     2     4     1     3
     2     4     3     1
     3     1     2     4
     3     1     4     2
     3     2     1     4

---

some additional remarks for the choice of N:

I made some test runs, where I used the loop above to find all permutations like perms does. For vector lengths of n=4 to n=7 and in each case N = factorial(n): 60-80% of the rows are unique. So for small n I would recommend to choose N as follows to be absolutely on the safe side:

N = min( [Q factorial(n)] )*2;

where Q is the number of permutations you want. For bigger n you either run out of memory while searching for all permutations, or the desired subset is so small compared to the number of all possible permutations that repetition is very unlikely! (Cosmic Ray theory linked by Luis Mendo)

Answer 3

Your requirements are very loose and allow many different possibilities. The most efficient solution I can think off that meets these requirements is as follows:

p = perms(1:6);
[p(1:128,:) repmat(7:32,128,1)]