Generate a matrix of combinations (permutation) without repetition (array exceeds maximum array size preference)

user_15551142 0
Viewed 151

I am trying to generate a matrix, that has all unique combinations of [0 0 1 1], I wrote this code for this:

v1 = [0 0 1 1];
M1 = unique(perms([0 0 1 1]),'rows');

• This isn't ideal, because perms() is seeing each vector element as unique and doing:

4! = 4 * 3 * 2 * 1 = 24 combinations.

• With unique() I tried to delete all the repetitive entries so I end up with the combination matrix M1 →

only [4!/ 2! * (4-2)!] = 6 combinations!

Now, when I try to do something very simple like:

n = 15;
i = 1;
v1 = [zeros(1,n-i) ones(1,i)];
M = unique(perms(vec_1),'rows');

• Instead of getting [15!/ 1! * (15-1)!] = 15 combinations, the perms() function is trying to do

15! = 1.3077e+12 combinations and it's interrupted.

• How would you go about doing in a much better way? Thanks in advance!

permutation matrix matlab arrays
1 Answers

You can use nchoosek to return the indicies which should be 1, I think in your heart you knew this must be possible because you were using the definition of nchoosek to determine the expected final number of permutations! So we can use:

idx = nchoosek( 1:N, k );

Where N is the number of elements in your array v1, and k is the number of elements which have the value 1. Then it's simply a case of creating the zeros array and populating the ones.

v1 = [0, 0, 1, 1];
N = numel(v1); % number of elements in array
k = nnz(v1);   % number of non-zero elements in array

colidx = nchoosek( 1:N, k );                  % column index for ones
rowidx = repmat( 1:size(colidx,1), k, 1 ).';  % row index for ones

M = zeros( size(colidx,1), N ); % create output
M( rowidx(:) + size(M,1) * (colidx(:)-1) ) = 1;

This works for both of your examples without the need for a huge intermediate matrix.

Aside: since you'd have the indicies using this approach, you could instead create a sparse matrix, but whether that's a good idea or not would depend what you're doing after this point.

user_39785450
Related