algorithm - 用 k 个 1 和 nk 个 0 扫描长度为 n 的二进制序列

Question

我想编写一个循环，用 k 1 和 nk 0 扫描所有长度为 n 的二进制序列。

实际上，在每次迭代中，都会对序列执行一个操作，如果满足某个条件，则循环将中断，否则进入下一个序列。（我不是在寻找nchoosek或者perms因为对于较大的 n 值，它需要很长时间才能给出输出）。

您建议使用什么 MATLAB 代码？

Answer 1

您可以实现类似迭代器/生成器模式的东西：

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

在上面的示例中，这将遍历所有长度为 4 的 0/1 序列，其中恰好 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