0

I'm trying to create a function that is able to go through a row vector and output the possible combinations of an n choose k without recursion.

For example: 3 choose 2 on [a,b,c] outputs [a,b; a,c; b,c]

I found this: How to loop through all the combinations of e.g. 48 choose 5 which shows how to do it for a fixed n choose k and this: https://codereview.stackexchange.com/questions/7001/generating-all-combinations-of-an-array which shows how to get all possible combinations. Using the latter code, I managed to make a very simple and inefficient function in matlab which returned the result:

function [ combi ] = NCK(x,k)
%x - row vector of inputs
%k - number of elements in the combinations

combi = [];
letLen = 2^length(x);

for i = 0:letLen-1

    temp=[0];
    a=1;

    for j=0:length(x)-1

        if (bitand(i,2^j))
            temp(k) = x(j+1);
            a=a+1;
        end
    end

    if (nnz(temp) == k)
        combi=[combi; derp];
    end
end
combi = sortrows(combi);
end

This works well for very small vectors, but I need this to be able to work with vectors of at least 50 in length. I've found many examples of how to do this recursively, but is there an efficient way to do this without recursion and still be able to do variable sized vectors and ks?

Community
  • 1
  • 1
Scoterster86
  • 3
  • 1

1 Answers1

2

Here's a simple function that will take a permutation of k ones and n-k zeros and return the next combination of nchoosek. It's completely independent of the values of n and k, taking the values directly from the input array.

function [nextc] = nextComb(oldc)
   nextc = [];
   o = find(oldc, 1);                 %// find the first one
   z = find(~oldc(o+1:end), 1) + o;   %// find the first zero *after* the first one
   if length(z) > 0
      nextc = oldc;
      nextc(1:z-1) = 0;
      nextc(z) = 1;                   %// make the first zero a one
      nextc(1:nnz(oldc(1:z-2))) = 1;  %// move previous ones to the beginning
   else
      nextc = zeros(size(oldc));
      nextc(1:nnz(oldc)) = 1;         %// start over
   end
end

(Note that the else clause is only necessary if you want the combinations to wrap around from the last combination to the first.)

If you call this function with, for example:

A = [1 1 1 1 1 0 1 0 0 1 1]
nextCombination = nextComb(A)

the output will be:

A =

   1   1   1   1   1   0   1   0   0   1   1

nextCombination =

   1   1   1   1   0   1   1   0   0   1   1

You can then use this as a mask into your alphabet (or whatever elements you want combinations of).

C = ['a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' 'i' 'j' 'k']
C(find(nextCombination))

ans = abcdegjk

The first combination in this ordering is

1   1   1   1   1   1   1   1   0   0   0

and the last is

0   0   0   1   1   1   1   1   1   1   1

To generate the first combination programatically,

n = 11; k = 8;
nextCombination = zeros(1,n);
nextCombination(1:k) = 1;

Now you can iterate through the combinations (or however many you're willing to wait for):

for c = 2:nchoosek(n,k)   %// start from 2; we already have 1
   nextCombination = nextComb(A);
   %// do something with the combination...
end

For your example above:

nextCombination = [1 1 0];
C(find(nextCombination))
for c = 2:nchoosek(3,2)
   nextCombination = nextComb(nextCombination);
   C(find(nextCombination))
end

ans = ab
ans = ac
ans = bc

Note: I've updated the code; I had forgotten to include the line to move all of the 1's that occur prior to the swapped digits to the beginning of the array. The current code (in addition to being corrected above) is on ideone here. Output for 4 choose 2 is:

allCombs =

   1   2
   1   3
   2   3
   1   4
   2   4
   3   4
beaker
  • 16,331
  • 3
  • 32
  • 49
  • After testing out your code it returns the right number of answers, but it doesn't go through all of the combinations. When I changed the vector to C=1:4; set next combination to [1 1 0 0] and did a 4 choose 2 it returned: [1,2; 1,3; 2,3; 2,4; 3,4; 1,2]. The nextCombination skips over 1,4 which causes it to duplicate the 1,2 at the end – Scoterster86 Jun 01 '15 at 14:03
  • @Scoterster86 Sorry about that, I had that line in my previous versions, but somehow it got left out. Also, if you use the `ideone` version, they seem to be having some clock issues at the moment that cause timestamp warnings to spew out on stderr. Shouldn't affect the execution of the script, though. – beaker Jun 01 '15 at 15:39