algorithm - 确定长度为m和汉明权重为r的二进制字符串的数量，这些二进制字符串可以包含连续的零(最大为k)

我在MatLab中有一个小问题。
我试图用给定的hamming权重r计算长度为m的二进制字的数目，它最多只包含k个连续的零。hamming weight是二进制字中非零项的数目。
我在论文的基础上实现了以下代码。

%% Different cases for the weight r
if (r==0)
    if (m<=k)
        numberOfBinaryStrings = 1;
    else
        numberOfBinaryStrings = 0;
    end
else

%% Computation of the number of binary strings
% Determination of the sum bound
bound = min(m,k);

d = k+1;
tmp = 0;

for j=0:bound
    for s=0:r-1
        if (m-j-1-s*d < r-1)
            bin1 = 0;
        else
            bin1 = nchoosek(m-j-1-s*d,r-1);
        end

        if (m-j-1-(k+1)-s*d < r-1)
            bin2 = 0;
        else
            bin2 = nchoosek(m-j-1-(k+1)-s*d,r-1);
        end

        tmp = tmp + (-1)^s * nchoosek(r-1,s) * ( bin1 - bin2 );
    end
end
numberOfBinaryStrings = tmp;

结束
对于给定的k和低字长以及Hamming权值r，该程序运行良好。在某些参数下，特别是大参数下，我得到了不应该是负的结果。
我已经尝试用gammaln函数替换nchoosek函数以避免溢出但在那里我也得到了负面的结果。
你知道我能做什么吗？谢谢您！

最佳答案

在Matlab中使用http://www.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic获取任意大小的整数。这将消除任何可能的溢出问题。
如果这不能解决你的问题，那么你在某个地方有一个逻辑错误。在这种情况下，我建议生成另一个解决方案，并尝试生成一个不同的最小示例。然后找出原因。
下面是python中的另一个解决方案，您可以使用它进行比较。

#! /usr/bin/env python

stored_word_counts = {}

def word_counts(word_length, ones, max_zero_run):
    if 0 == ones:
        if max_zero_run < word_length:
            # Impossible.
            return 0
        else:
            # String of all zeros.
            return 1
    key = (word_length, ones, max_zero_run)
    if key not in stored_word_counts:
        # We will try all places we can put a 1.
        mid = (ones+1)/2 # Cut in half, round up.
        ones_before = mid - 1
        ones_after = ones - mid
        stored_word_counts[key] = sum(
                word_counts(pos, ones_before, max_zero_run) * word_counts(word_length - pos - 1, ones_after, max_zero_run)
                    for pos in xrange(ones_before, word_length - ones_after)
                )
    return stored_word_counts[key]

print(word_counts(50, 20, 5)) # Change this line as needed.

关于algorithm - 确定长度为m和汉明权重为r的二进制字符串的数量，这些二进制字符串可以包含连续的零(最大为k)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45171613/