Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

How can i get all the possible combinations of elements of a matrix?i dont want elements of the same column.i want to create vectors whose sum is smaller than a number

Asked by NIKOS on 22 Jan 2014
Latest activity Commented on by NIKOS on 14 Feb 2014

i dont want elements of the same column. i want to create vectors whose sum is smaller than a number and put them in a new matrix

4 Comments

Azzi Abdelmalek on 22 Jan 2014

You can also give a short example to illustrate what you want

NIKOS on 22 Jan 2014

the size of the given matrix is not standard.it will be given as input to the problem.All elements are positive integers.the columns of the matrix represent different kind of sources.So if the matrix has 3 columns i am looking for combinations of 3 elements.each combination must have one element of each column.The sum of each combination must be smaller than a number.this number will be given as input too.

N = 50; k = 4; d = zeros(N,k);

for i = 2:k

   for j = 1:N
        if (i-2+j) <= N-1
            d(j,i) = i-2+j; 
        else
            d(j,i) = 0;
        end
    end
end

this is the matrix i created.

NIKOS on 22 Jan 2014

this is an example of what i want.but it is made to run only for k=4.i want to generalize it to run for every input to k variable

g=zeros(1,4); N=50; j=1; g(1)=0;

for k = g(1)+1 :N

 g(2) = k;
    for m = g(2)+1:N
        g(3) = m;
        for w = g(3)+1:N
            g(4) = w;
            if sum(g) <= N-1
                G(j,:) = g;
                j = j+1;
            end
        end
    end

end

NIKOS

Products

No products are associated with this question.

2 Answers

Answer by Roger Stafford on 13 Feb 2014

I had put your problem aside, Nikos, and only got around to working it out today. I have taken one liberty with your request. In the G matrix of your last example the first element was always set to a fixed zero value which seems rather useless to bother with, so in this routine that first element is allowed to increase above zero. Therefore the rows of G will contain all possible sequences of n elements in which each element is a non-negative integer greater than the previous element and for which their entire sum is less than the number N. The rows of G will be in lexicographical order. You may enter any value of n you wish (provided there is enough memory to hold the resulting G.) You will note that this routine appears to repeat itself once. That is because I could discover no easy formula for the required number of rows in G in terms of N and n, so the first pass simply makes a count of the necessary number the brute force way, and then allocates the proper amount of memory space for G. On the second pass it proceeds to fill G. This is admittedly rather repetitious, but it beats trying to concatenate rows onto an unallocated G one-row-at-a-time, which could slow you down rather seriously for large values of N and n.

 N = 33;  % Set N and n to your desired values
 n = 5;
 N2 = N - n*(n-1)/2;
 for p = 1:2
   a = -ones(1,n);
   s = -ones(1,n);
   k = 1;
   j = 0;
   while k >= 1
     if s(k)+1+(a(k)+1)*(n-k) < N2
       a(k:n) = repmat(a(k)+1,1,n-k+1);
       s(k:n) = cumsum([s(k)+1,a(k+1:n)]);
       k = n;
       j = j + 1;
       if p == 2  % Wait for the second pass to fill G
         G(j,:) = a;
       end
     else
       k = k - 1;
     end
   end
   if p == 1  % Allocate space for G at the end of the first pass
     G = zeros(j,n);
   end
 end
 G = G + repmat(0:n-1,size(G,1),1);

3 Comments

NIKOS on 14 Feb 2014

thank you for your time.in the meanwhile i found a function for the problem A=combnk(1:N-1,k-1) where N=rows kai k=columns

Roger Stafford on 14 Feb 2014

The 'combnk' function does not produce the same result as the one you described, Nikos, and the one I have coded for you. In particular it does not give all possible combinations whose sum is less than a number N. I suggest you try and compare them to see for yourself their differences.

NIKOS on 14 Feb 2014

you are right.i wrote only the first step.

j=1;

   for i=1:length(A)
     if (sum(A(i,:))<=N-1)
         G(j,:)=A(i,:);
              j=j+1;
   end

end

Roger Stafford
Answer by Roger Stafford on 14 Feb 2014

Nikos, there is a better way of determining the number of rows in G. It is not a formula but involves an iteration that is much quicker that making two passes as the other method does. Here is the complete code:

 N = 82; % Choose the desired N. It must be greater than n*(n-1)/2
 n = 12; % Choose n
 N2 = N - n*(n-1)/2;
 C = zeros(N2,n); % Set up a table for computing the number of combinations
 C(:,1) = (1:N2)';
 for k = 2:n
   for q = 1:N2
     C(q,k) = sum(C(q:-k:1,k-1));
   end
 end % C(N2,n) has the number of combinations at exit here
 G = zeros(C(N2,n),n); % Now we can allocate memory for G
 a = -ones(1,n);
 s = -ones(1,n);
 k = 1;
 j = 0;
 while k >= 1
   if s(k)+1+(a(k)+1)*(n-k) < N2
     a(k:n) = repmat(a(k)+1,1,n-k+1);
     s(k:n) = cumsum([s(k)+1,a(k+1:n)]);
     k = n;
     j = j + 1;
     G(j,:) = a;
   else
     k = k - 1;
   end
 end
 G = G + repmat(0:n-1,size(G,1),1);

0 Comments

Roger Stafford

Contact us