计数和生成序列
4.00/5 (2投票s)
本文描述了生成和计数序列的技术
引言
本文旨在介绍一些用于计算和生成特定长度（例如，基于比特或十进制数字）字母表上的固定长度序列的算法和分析技术。
为了使表述更易于理解，我们将考虑以下问题。
问题 1： 给定两个正整数 n 和 k ，其中 k ≤ n ，计算（或列出）所有长度为 n 且不包含 k 个连续 1 的比特字符串。
问题 2： 给定两个正整数 n 和 k ，计算（或列出）所有长度为 n 且数字之和为 k 的十进制数字字符串。
讨论将探讨使用（带有剪枝的）蛮力搜索进行枚举，以及使用递推方程进行计数和枚举。
此外，我们将讨论使用容斥原理来解决这些问题的某些特定实例。
各种算法都已在 HTML 页面中用 JavaScript 编码，可以从此处访问。上图显示了从浏览器访问该页面时的屏幕快照。虽然 JavaScript 与编译型语言相比速度较慢，但浏览器环境具有快速开发和测试的优点。
带有剪枝的蛮力搜索
蛮力（穷举）搜索可用于生成（枚举）所有长度为 n 的序列（向量）。使用此技术，将逐个生成长度为 n 的序列，并对每个序列进行资格测试（即，它是否满足问题约束）。
为了生成指定长度 n 的序列，我们可以使用“填槽”的过程。序列表示为数组 S[1..n ]。每个数组分量 S[i ] 代表一个槽，可以用预定义集合 A 中的一个值来填充。此过程可以通过以下递归过程实现（这假设数组是从编号最低的槽到编号最高的槽按顺序填充的）
SlotFill(i,n))
{ for each value v in A
{ fill the i-th slot in S with v;
if i = n then
{ if ValidSolution(S) then Print(S); }
else SlotFill(i+1) // SlotFill the remaining slots
}
}
对于更具体的示例，以下代码将打印所有长度为 n 的 2n 个比特字符串。
SlotFill(i,n))
{ for(k=0; k ≤1; k++)
{ S[i] = k;
if i = n then
{ Print(S); }
else SlotFill(i+1) // SlotFill the remaining slots
}
}
令人惊讶的是，前面的代码实际上会打印出所有长度为 n 的可能比特字符串。程序首先打印序列 00...0，然后最深的递归调用返回，其父调用继续执行，并将第 n 个槽填充为比特值 1，并打印序列 00...01，依此类推。
早期剪枝很有帮助
通常，对于大多数问题，搜索空间非常大，需要很长时间才能探索完。因此，最好避免在发现部分解向量违反问题约束时立即进行扩展。
[注意：这种带有剪枝的蛮力搜索技术被称为“回溯”。]
这通常使用一个辅助函数 ValidSolution() 来实现，该函数用于测试部分解向量是否符合问题的约束。
因此，前面的蛮力搜索骨架代码可以修改为以下代码（假设每个槽都将用 1 到 k 之间的整数填充，并且解向量使用全局数组 S[1..n ] 定义）。
void SlotFill(int pos, int n)
{ for slotval = 1 to k
{ if (sf_flag) return; // to terminate if only one solution is desired
S[pos] = slotval; // Fill the slot at position pos
if ValidSolution(S,pos) // Check if partial solution S[1..pos] is valid
{ // Check if solution is complete
if (pos == n) // Solution found
{ sf_flag = true; Print(S); }
else // "pos < n" is implied; Advance to next slot
SlotFill(pos+1,n);
}
}
}
作为测试部分向量的替代方法，我们可以在填槽时过滤可能值集。对于问题 1，这意味着：在用“1”填槽时，检查前面的 k -1 个位置，如果发现前面的 k -1 个比特都为 1，则跳过填充。
基于上述思路，下面的列表显示了使用带有剪枝的蛮力搜索解决问题 1 的程序代码。
// Sample initial call: SlotFill_Bits(1,10,3) to generate
// bit strings of length 10 not containing 3 consecutive 1s
var S; // the array object
function SlotFill_Bits(pos, n, k)
{ for(var slotval = 0; slotval < 1; slotval++)
{ if ((slotval==1) && (pos >= k))
if (Filter(S,pos,k)) continue;
S[pos] = slotval; // Fill the slot at position pos
{ // Check if solution is complete
if (pos == n) // Solution found
{ Print(S); }
else SlotFill_Bits(pos+1,n,k);
}
}
}
function Filter(S,pos,k)
{ // check if any of the previous k-1 positions is 0
for(var i=pos-1; i > pos-k; i--)
{ if (S[i] ==0) return false; }
return true;
}
var OutStr=""; // Output vector as a string of list items
function Print(S)
{ OutStr += "<li>" + S.join("") + "</li>"; }
使用递推方程
此方法对于计数字符串特别有用。它也可用于枚举。为了帮助理解此技术，我们将举一个例子（问题 1 的一个特殊情况， k =2）。
示例 1： 推导 R(n ) 的必要递推方程，R(n ) 是长度为 n 且不包含两个连续 1 的比特字符串的数量。
证明
如前所述，长度为 n 的比特字符串可以由 0/1 数组 S[1..n ] 表示。
令 R(n ) 表示长度为 n 且不包含两个连续 1 的比特字符串的数量。让我们尝试将 R(n ) 与 R(n -1)（或一般地，与 R(k )，其中 k < n ）关联起来。考虑填槽最左侧的两种情况，如上图所示。如果此槽填充为 0，则剩余的 n -1 个槽不得包含两个连续的 1；根据定义，此类字符串的数量为 R(n -1)。另一方面，如果最左侧的槽填充为 1，则下一个槽只能填充为 0（以避免连续的 1），并且剩余的 n -2 个槽不得包含两个连续的 1；此类字符串的数量由 R(n -2) 给出。因此，我们得出结论 R(n ) = R(n -1) + R(n -2)（回想一下求和规则 |A∪B| = |A|+|B|-|A∩B|，在本例中 A∩B 为空集）。
我们需要两个基本步骤。R(1) = 2，因为长度为 1 的两个二进制字符串都是可接受的。同样，R(2) = 3，因为我们要计算字符串 00、01 和 10。根据前面的分析，我们可以编写以下递归方法来计算 R(n )
// The function R returns the number of bit strings of length n
// that do not contain two consecutive 1s
function R(n)
{ if (n == 1) return 2;
else if (n == 2) return 3;
else return R(n-1)+R(n-2);
}
警告： 对于 n > 30，前面的函数将花费很长时间（数天）才能完成。这是因为存在两个递归调用 R(n -1) 和 R(n -2)，这导致了过多的过程调用；具有相同输入参数的某些调用会遇到不止一次（例如，在计算 R(4) 时，R(2) 被调用两次）。此问题可以通过将递归转换为迭代来解决，如以下代码所示。
function R_Iterative(n)
{ if (n == 1) return 2;
else if (n == 2) return 3;
var A = new Array();
A[0]=2;
A[1]=3;
for(var i=2; i < n; i++)
{ A[i%2] = A[(i-1)%2] + A[(i-2)%2]; }
return A[(n-1)%2] ;
}
示例 2： 推导 R(n,k ) 的必要递推方程，R(n,k ) 是长度为 n 且不包含 k （其中 k ≤ n ）个连续 1 的比特字符串的数量。
证明
考虑以 0 或 10 或 110，...，或 11...10（即，以 k -1 个 1 开头）开头的比特字符串。对于这些字符串中的其余比特，我们必须没有 k 个连续的 1。因为这些字符串是所有要计数的字符串 [注意：任何以 k 个连续 1 开头的字符串都必须排除]，我们得出 R(n,k ) 的以下递推方程
R(n,k ) = R(n-1,k ) + R(n-2,k ) + ... + R(n-k ,k )
作为基本步骤，我们可以论证以下方程
1. 如果 n < k ，则 R(n,k ) = 2n ，因为所有长度小于 k 的比特字符串都是可接受的
2. 如果 n = k ，则 R(n,k ) = 2n -1，因为对于 n = k ，我们只需要排除一个字符串（即包含 k 个 1 的字符串）。
前面的方程可以编码为以下 JavaScript 函数：（在我们的 JavaScript 代码中，它被命名为 R1，以区别于其他函数。）
// The function R1(n,k) returns the number of bit strings of length n
// that do not contain k consecutive 1s
function R1(n,k)
{ if (n < k) return Math.pow(2,n);
else if (n == k) return Math.pow(2,n)-1;
else
{ var sum =0;
for(var i = 1; i ≤ k; i++)
{ sum += R1(n-i,k); }
return sum;
}
}
从递推进行枚举
如果您深入思考示例 1（或示例 2）的递推方程，您可能会想到以下问题：“难道我们不能使用解决方案数量的递推方程来生成实际的解决方案吗？”事实确实如此，我们将其作为一条原则。
枚举原理： 解决方案数量的递推方程可以重写为生成实际解决方案的算法。
此外，此方法由于生成满足约束的解决方案而不是其他解决方案，因此预计会比生成更大集合的解决方案然后过滤的方法更有效。
重构示例 1 的递推方程以进行枚举
对于程序代码，我们只需将填槽编码为递归方法，模仿图 1 中所示的过程（和伴随的证明）。
我们将假设解向量由全局 0/1 数组 S[1..n ] 编码。因此，我们只需要一个输入参数 n ，它表示当前要填充的槽的位置。填充从第 n 个槽开始向下进行，直到到达第一个槽。此时，我们得到一个完整的解向量，并打印出来。
// The function SlotFill_Rec(n) prints bit strings of length n that
// do not contain two consecutive 1s
// Initial call: SlotFill_Rec(n), where n is the length of binary strings
// Uses a global array S[1..n]
function SlotFill_Rec(n)
{ if (n == 1)
{ S[1]=0; Print(S); S[1]=1; Print(S); }
else if (n == 2)
{ S[1]=0; S[2]=0; Print(S);
S[1]=0; S[2]=1; Print(S);
S[1]=1; S[2]=0; Print(S);
}
else
{ S[n]=0; SlotFill_Rec(n-1);
S[n]=1; S[n-1]=0; SlotFill_Rec(n-2);
}
}
问题 2 的递推和枚举
我们将此作为另一个示例。
示例 3： 推导问题 2 中定义的 R(n,k ) 的递推方程。使用这些方程编写一个程序函数来生成相应的字符串。
递推证明
令 R(n,k ) 表示长度为 n 且数字之和为 k 的十进制数字字符串的数量。如果最左侧的槽用数字 d 填充，则剩余的 n -1 个槽的数字之和必须为 k - d ；根据定义，此类字符串的数量为 R(n -1,k - d )。因为最左侧的槽有 10 种可能的填充值，所以 R(n,k ) = R(n -1,k ) + R(n -1,k -1) + ... + R(n -1,k -9)
作为基本步骤，我们有 R(1,k ) = 1，如果 k 是 0-9 的数字值之一；否则，R(1,k ) = 0。
基于上述证明，我们可以编写以下递归函数来计算 R(n,k )（在我们的 JavaScript 代码中，它被命名为 R2，以区别于其他函数。）
// The function R2(n, k) returns the number of decimal
// strings of length n whose sum of digits = k
function R2(n, k)
{ if (n == 1)
{ if (( k >= 0) && (k ≤ 9)) return 1;
else return 0;
}
// else here can be committed (why?)
var count=0;
for(var digit=0; digit ≤ 9; digit++)
{ count += R2(n-1, k-digit); }
return count;
}
上述递推可以表示为以下用于枚举相应字符串的函数。
// The function SlotFill_Digits(n,k) prints decimal strings of length n
// whose sum of digits = k
// Uses a global array S[1..n]
function SlotFill_Digits(n, k)
{ if (n == 1)
{ if (( k >= 0) && (k ≤ 9))
{ S[1]=k; Print(S); }
}
else
for(var digit=0; digit ≤ 9; digit++)
{ S[n]= digit; SlotFill_Digits(n-1, k-digit); }
}
其他分析技术
可以使用容斥原理来生成满足特定约束的序列数量的公式。我们将针对问题 2 的特定实例演示这一点。
示例 4： 计算长度为 4 且数字之和为 25 的所有十进制数字字符串。
读者可以使用托管页面（见顶部图）来验证此实例的答案是 348。
以下解释显示了一种使用组合（带重复）和容斥原理的解决方案。
长度为 4 且数字之和为 25 的（十进制数字）字符串的数量等于以下方程的解的数量
X1+ X2+ X3+ X4= 25,
其中 Xi 是整数变量且 0 ≤ Xi ≤ 9。
当 Xi 没有限制（除了 Xi 为非负数）时的解的数量是组合（带重复）问题，等同于分配 25 个星号和 3 个隔板（变量数减 1），即 Comb(25+3,3)。
为了处理受限问题，我们使用集合补集。原始问题解集 = 所有（无限制）解 - 所有 Xi ≤ 9 的解的补集。
因此，从数量上看，我们有以下关于 N （原始问题解的数量）的方程
N = |所有解| -|A ∪ B ∪ C ∪ D|，其中
A 是 X1 ≥ 10 的解集，
B 是 X2 ≥ 10 的解集，
C 是 X3 ≥ 10 的解集，
D 是 X4 ≥ 10 的解集。
根据容斥原理，
|A ∪ B ∪ C ∪ D| = |A|+ |B|+ |C| + |D| - [|A∩B| + |A∩C|+ |A∩D|+ |B∩C|+ |B∩D|+ |C∩D|] + [|A∩B∩C| + |A∩B∩D|+|A∩C∩D| + |B∩C∩D|] - |A∩B∩C∩D|
单个集合 A、B、C 或 D 对应于其中一个 Xi ≥ 10（预留 10 个星号并将剩余的 15 个星号分配给四个变量，Comb(15+3,3)。（注意此情况发生 4 次。）
两个集合的交集对应于其中两个 Xi ≥ 10（预留 20 个星号并将剩余的 5 个星号分配给四个变量，Comb(5+3,3)。（注意此情况发生 Comb(4,2)= 6 次。）
三个集合的交集，对应于其中三个 Xi ≥ 10，计算结果为 0（因为这需要至少 30 个星号）。
因此，我们得出结论 N = Comb(25+3,3) - 4×Comb(15+3,3) + 6×Comb(5+3,3) = (28*27*26)/(3*2*1) - 4×(18*17*16)/(3*2*1) + 6×(8*7*6)/(3*2*1) = 384。