CODEWITHSUNDEEP
algorithmmatlabcombinations
Scoterster86
Scoterster86

Reputation: 3

All possible N choose K WITHOUT recusion

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?

Upvotes: 0

Views: 906

Answers (1)

beaker
beaker

Reputation: 16801

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

Upvotes: 2

Related Questions