Lexicographic ranking of vectors

Hello everyone!

I have the following problem. I have an Nx2^N matrix of zeros and ones and I want to rearrange the columns as follows. First, in ascending order according to the column sum. Second, I want all columns that give the same column sum to be ordered AS VECTORS from greatest to smallest according to the lexicographical order (according to which vector x is greater than or equal to vector y if there is some j<=N such that x(i)=y(i) for all i<j (if any) and x(j)>y(j)).

For example, if the original matrix is:

A=[0    0    0    0    1    1    1    1;
   0    0    1    1    0    0    1    1;
   0    1    0    1    0    1    0    1]

(for N=3) I want to obtain:

B=[0    1    0    0    1    1    0    1;
   0    0    1    0    1    0    1    1;
   0    0    0    1    0    1    1    1]

Thanks! Alejandro

Answer 1

[Doug Hull]

If the matrix is the size you describe, and there are presumably all unique vectors, then I think all the options will be represented uniquely.

If that is the case, instead of 'sorting' the vectors, can you just 'generate' them all? It seems like it would be relatively easy to make a function to do this.

Here is some starter code:

flipud(sortrows(unique(perms([0 0 0]),'rows')))
flipud(sortrows(unique(perms([0 0 1]),'rows')))
flipud(sortrows(unique(perms([0 1 1]),'rows')))
flipud(sortrows(unique(perms([1 1 1]),'rows')))

[Alejandro]

Indeed, all options are represented uniquely. So yes, generating the vectors in the desired order is easier than sorting an existing matrix and your suggestion works perfectly.

Thanks a lot!