algorithm - 长度为m、汉明权重为r的二进制串个数的确定，最多可以包含连续的k个零

Question

我在 MatLab 中遇到了一个小问题。

我正在尝试计算具有给定汉明权重 r 的长度为 m 的二进制字的数量，其中最多只包含 k 个连续的零。汉明权重是二进制字中非零项的个数。

我根据论文 "Constant-Weight and Constant-Charge Binary Run-Length Limited Codes" (Kurmaev) 实现了以下代码.

%% 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 和低字长以及汉明权重 r，该代码运行良好。在某些参数上，尤其是大参数，我得到了负面结果，这是不应该的。我已经尝试用 gammaln 函数替换 nchoosek 函数以避免溢出。但我也得到了负面结果。

你知道我能做什么吗？谢谢你!

Answer 1

使用http://www.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic在 Matlab 中获取任意大小的整数。这应该可以消除任何可能的溢出问题。

如果这不能解决您的问题，那么您的某处存在逻辑错误。在那种情况下，我会建议产生另一个解决方案，并尝试产生一个不同的最小示例。然后尝试找出原因。

这是 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.