scanning binary sequences of length n with k 1's and n-k 0's

Question

I want to write a loop that scans all binary sequences of length n with k 1's and n-k 0's.

Actually, in each iteration an action is performed on the sequence and if a criterion is met the loop will break, otherwise it goes to next sequence. (I am not looking for nchoosek or perms since for large values of n it takes so much time to give the output).

What MATLAB code do you suggest?

Answer 1

You could implement something like an iterator/generator pattern:

classdef Iterator < handle
    properties (SetAccess = private)
        n              % sequence length
        counter        % keeps track of current iteration
    end

    methods
        function obj = Iterator(n)
            % constructor
            obj.n = n;
            obj.counter = 0;
        end

        function seq = next(obj)
            % get next bit sequence
            if (obj.counter > 2^(obj.n) - 1)
                error('Iterator:StopIteration', 'Stop iteration')
            end
            seq = dec2bin(obj.counter, obj.n) - '0';
            obj.counter = obj.counter + 1;
        end

        function tf = hasNext(obj)
            % check if sequence still not ended
            tf = (obj.counter <= 2^(obj.n) - 1);
        end

        function reset(obj)
            % reset the iterator
            obj.counter = 0;
        end
    end
end

Now you can use it as:

k = 2;
iter = Iterator(4);
while iter.hasNext()
    seq = iter.next();
    if sum(seq)~=k, continue, end
    disp(seq)
end

In the example above, this will iterate through all 0/1 sequences of length 4 with exactly k=2 ones:

 0     0     1     1
 0     1     0     1
 0     1     1     0
 1     0     0     1
 1     0     1     0
 1     1     0     0