сканирование двоичных последовательностей длины n с k 1 и n-k 0's

Question

Я хочу написать цикл, который сканирует все двоичные последовательности длины n с k 1 и n-k 0.

Фактически, на каждой итерации выполняется действие над последовательностью, и если выполняется критерий, цикл прерывается, в противном случае он переходит к следующей последовательности. (Я не ищу nchoosek или perms, так как для больших значений n требуется столько времени, чтобы дать результат).

Какой код MATLAB вы предлагаете?

Answer 1

Вы могли бы реализовать что-то вроде iterator/generator схеме:

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 

Теперь вы можете использовать его как:

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

В приведенном выше примере, это будет перебирать все 0/1 последовательностей длины 4 с точно k = 2 единиц:

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