-2

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?

Amro
  • 123,847
  • 25
  • 243
  • 454
Mahdi Khosravi
  • 129
  • 6

1 Answers1

2

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
Amro
  • 123,847
  • 25
  • 243
  • 454
  • Thank you very much. It seems nice. For the case I'm facing I must skip the cases where the number of 1's is not the desired k? Or there is a better solution? – Mahdi Khosravi Sep 24 '13 at 07:09
  • you could add a test to the loop: `if sum(seq)~=k, continue, end` – Amro Sep 24 '13 at 07:12
  • Is there any way to make it faster? Unfortunately, `nchoosek` works much faster – Mahdi Khosravi Sep 24 '13 at 07:41
  • did you look at the answers in the question I linked to, there are some very clever ideas. If you absolutely want speed, just implement the previous suggestions in C/C++ as a MEX-function and call it in your code... – Amro Sep 24 '13 at 07:58