从输出重构编码器的输入
Reconstructing input to encoder from output
我想了解如何解决 Codility ArrayRecovery 挑战，但我什至不知道要参考哪个知识分支。是组合学、优化、计算机科学、集合论还是其他？
编辑：
要咨询的知识分支是 constraint programming, particularly constraint propagation. You also need some combinatorics 知道如果你一次从 [1..n[=110= 范围内取 k 个数字]], 限制是没有数字可以比它前面的数字大，结果是
(n+k-1)!/k!(n-1)! 可能的组合
这与一次 k 的 n 事物的 替换 的组合数量相同，它具有数学符号
Peter Norvig 提供了一个很好的例子来说明如何用他的 Sudoku solver.
解决这类问题
您可以通过上面的 link 阅读 ArrayRecovery 问题的完整描述。简而言之，有一个 编码器 接受范围为 1 的 整数序列 到某个给定的限制（比如我们的目的是 100 ) 和 对于输入序列的每个元素 输出 最近看到的小于当前输入的整数，或者如果 none 存在则为 0.
input 1, 2, 3, 4 => output 0, 1, 2, 3
input 2, 4, 3 => output 0, 2, 2
完整的任务是，给定输出（以及允许输入的范围），找出有多少可能的输入可以生成它。但在我开始计算之前，我对如何制定方程式没有信心。这就是我寻求帮助的原因。 （当然，如果有解释，也欢迎提供完整的解决方案。）
我只是看看一些可能的输出并想知道。这里有一些示例编码器输出和我能想到的输入，* 表示任何有效输入，> 4 表示任何大于 4 的有效输入。如果需要，输入被称为 A1, A2, A3, ...（基于 1 的索引）
编辑#2
我在这个挑战中遇到的部分问题是我没有为输出手动生成完全正确的可能输入集。我相信下面的设置现在是正确的。如果您想查看我之前的错误，请查看此答案的编辑历史。
output #1: 0, 0, 0, 4
possible inputs: [>= 4, A1 >= * >= 4, 4, > 4]
output #2: 0, 0, 0, 2, 3, 4 # A5 ↴ See more in discussion below
possible inputs: [>= 2, A1 >= * >=2, 2, 3, 4, > 4]
output #3: 0, 0, 0, 4, 3, 1
possible inputs: none # [4, 3, 1, 1 >= * > 4, 4, > 1] but there is no number 1 >= * > 4
与第一个输入序列相比，第二个输入序列的约束非常严格，只是增加了 2 个输出。第三个序列被限制得不可能。
但是示例 #2 中 A5 的一组约束有点难以表达。当然A5 > O5，这是对所有输入的基本约束。但是任何 > A4 和 O5 之后的输出都必须出现在 A4 之后的输入中，因此 A5 必须是 A5 之后也 > A4 的数字集中的一个元素。由于只有 1 个这样的数字 (A6 == 4)，因此必须是 A5，但如果后面有更长的数字串，它会变得更复杂。 （编者按：其实不是。）
随着输出集越来越长，我担心这些约束会变得越来越复杂，越来越难以正确处理。我想不出有任何数据结构可以有效地表示这些数据，从而有效地计算出可能的组合数量。我也不太明白如何通过算法将约束集添加在一起。
这是我目前看到的任何给定 An
的约束
- An > On
- An <= min（从 O1 到 n-1[= 的其他可能数字集116=] > On)。如何定义大于On的可能数集合？
- 在输入
中最近出现 On 之后大于 On 的数字
- An >= max(从 O1 到 n-1[= 的其他可能数字集116=] < On)。如何定义小于On的可能数集合？
- 实际上这个集合是空的，因为根据定义，On 是前一个输入序列中最大的可能 数。 （这并不是说它严格来说是前一个输入序列中最大的数字。）
- 输入中最后一次出现之前出现的任何小于 On 的数字都不符合条件，因为 "nearest" 规则。由于 "nearest" 规则和可传递的 属性：如果 Ai < On 和 Aj < Ai 那么 Aj < On
- 然后是集合论：
- An 必须是 On+1 到 Om，其中 m 是满足 Om < On 的最小 m > n。在这样的 Om 之后并且大于 Om （An 是）的任何输出都必须出现在 Am.
之后或之后
- 如果一个元素出现在输出中但没有出现在输入中与输出的其余部分一致的位置，则该元素未被解释。显然我需要比这更好的定义，以便编写代码和算法来计算它。
似乎某种集合论 and/or 组合学或线性代数可能有助于计算可能的序列数量，这些序列将解释所有未解释的输出并满足其他约束条件. （编者按：其实，事情永远不会变得那么复杂。）
这是一个主意。构造输出的一种已知方法是使用堆栈。我们在元素大于或等于时弹出它，然后输出较小的元素（如果存在），然后将较大的元素压入堆栈。现在，如果我们尝试从输出向后执行此操作怎么办？
首先我们将使用 c∅dility 示例演示堆栈方法。
[2, 5, 3, 7, 9, 6]
2: output 0, stack [2]
5: output 2, stack [2,5]
3: pop 5, output, 2, stack [2,3]
7: output 3, stack [2,3,7]
... etc.
Final output: [0, 2, 2, 3, 7, 3]
现在让我们尝试重建！我们将使用 stack 作为假想堆栈和重构输入：
(Input: [2, 5, 3, 7, 9, 6])
Output: [0, 2, 2, 3, 7, 3]
* Something >3 that reached 3 in the stack
stack = [3, 3 < *]
* Something >7 that reached 7 in the stack
but both of those would've popped before 3
stack = [3, 7, 7 < x, 3 < * <= x]
* Something >3, 7 qualifies
stack = [3, 7, 7 < x, 3 < * <= x]
* Something >2, 3 qualifies
stack = [2, 3, 7, 7 < x, 3 < * <= x]
* Something >2 and >=3 since 3 reached 2
stack = [2, 2 < *, 3, 7, 7 < x, 3 < * <= x]
让我们试试你的例子：
示例 1：
[0, 0, 0, 2, 3, 4]
* Something >4
stack = [4, 4 < *]
* Something >3, 4 qualifies
stack = [3, 4, 4 < *]
* Something >2, 3 qualifies
stack = [2, 3, 4, 4 < *]
* The rest is non-increasing with lowerbound 2
stack = [y >= x, x >= 2, 2, 3, 4, >4]
示例 2：
[0, 0, 0, 4]
* Something >4
stack [4, 4 < *]
* Non-increasing
stack = [z >= y, y >= 4, 4, 4 < *]
计算组合的数量是通过将所有部分的可能性相乘来实现的。一个部分是一个有界的单细胞；或一个或多个单元格的绑定、非增加子数组。为了计算后者，我们使用多项选择二项式 (n + k - 1) choose (k - 1)。考虑到我们可以将 3 单元格的绑定非增加序列的单元格之间的差异表示为：
(ub - cell_3) + (cell_3 - cell_2) + (cell_2 - cell_1) + (cell_1 - lb) = ub - lb
那么将 ub - lb 分配到 (x + 1) 个单元格的方法数是
(n + k - 1) choose (k - 1)
or
(ub - lb + x) choose x
For example, the number of non-increasing sequences between
(3,4) in two cells is (4 - 3 + 2) choose 2 = 3: [3,3] [4,3] [4,4]
And the number of non-increasing sequences between
(3,4) in three cells is (4 - 3 + 3) choose 3 = 4: [3,3,3] [4,3,3] [4,4,3] [4,4,4]
（解释归因于 Brian M. Scott。）
粗略的JavaScript草图（代码不可靠，只是为了说明编码。编码器列出了[lower_bound，upper_bound]，或者一个非递增序列作为[non_inc, 长度, lower_bound, upper_bound]):
function f(A, M){
console.log(JSON.stringify(A), M);
let i = A.length - 1;
let last = A[i];
let s = [[last,last]];
if (A[i-1] == last){
let d = 1;
s.splice(1,0,['non_inc',d++,last,M]);
while (i > 0 && A[i-1] == last){
s.splice(1,0,['non_inc',d++,last,M]);
i--
}
} else {
s.push([last+1,M]);
i--;
}
if (i == 0)
s.splice(0,1);
for (; i>0; i--){
let x = A[i];
if (x < s[0][0])
s = [[x,x]].concat(s);
if (x > s[0][0]){
let [l, _l] = s[0];
let [lb, ub] = s[1];
s[0] = [x+1, M];
s[1] = [lb, x];
s = [[l,_l], [x,x]].concat(s);
}
if (x == s[0][0]){
let [l,_l] = s[0];
let [lb, ub] = s[1];
let d = 1;
s.splice(0,1);
while (i > 0 && A[i-1] == x){
s =
[['non_inc', d++, lb, M]].concat(s);
i--;
}
if (i > 0)
s = [[l,_l]].concat(s);
}
}
// dirty fix
if (s[0][0] == 0)
s.splice(0,1);
return s;
}
var a = [2, 5, 3, 7, 9, 6]
var b = [0, 2, 2, 3, 7, 3]
console.log(JSON.stringify(a));
console.log(JSON.stringify(f(b,10)));
b = [0,0,0,4]
console.log(JSON.stringify(f(b,10)));
b = [0,2,0,0,0,4]
console.log(JSON.stringify(f(b,10)));
b = [0,0,0,2,3,4]
console.log(JSON.stringify(f(b,10)));
b = [0,2,2]
console.log(JSON.stringify(f(b,4)));
b = [0,3,5,6]
console.log(JSON.stringify(f(b,10)));
b = [0,0,3,0]
console.log(JSON.stringify(f(b,10)));
下面的代码通过了 Codility 的所有测试。 OP 添加了一个 main 函数以在命令行上使用它。
约束并不像 OP 想象的那么复杂。特别是，在任何情况下，您都不需要添加限制，即输入是输出中其他地方出现的某些特定整数集的元素。每个输入位置都有明确定义的最小值和最大值。
该规则的唯一复杂之处在于，有时最大值是 "the value of the previous input"，并且输入本身有一个范围。但即便如此，所有类似的值都是连续的并且具有相同的范围，因此可以使用基本组合学计算可能性的数量，并且这些输入作为一个组独立于其他输入（仅用于设置范围） , 因此该组的可能性可以通过简单的乘法与其他输入位置的可能性相结合。
算法概述
该算法在每个 span 之后单次通过输出数组更新输入数组的可能数量，这就是我所说的输出中数字的重复。 （您可能会说每个元素都相同的输出的最大子序列。）例如，对于输出 0,1,1,2，我们有三个跨度：0、1,1 和 2。当新的跨度开始时，将计算前一个跨度的可能性数。
这个决定是基于一些观察：
- 对于长度大于1的spans，输入的最小值
允许在第一个位置是输入的任何值
在第二个位置。计算一个可能性的数量
跨度是简单的组合，但标准公式
需要知道数字的范围和跨度的长度。
- 每次值
输出变化（和一个新的跨度存在），强烈限制了前一个跨度的值：
- 当输出上升时，唯一可能的原因是之前的输入是新的更高输出的值，而新的更高输出的位置对应的输入更高。
- 当输出下降时，会建立新的约束，但这些约束有点难以表达。该算法存储 stairs（见下文）以量化输出下降时施加的约束
此处的目的是限制每个 span 的可能值范围。一旦我们准确地做到这一点，计算组合的数量就很简单了。
因为编码器回溯寻找以两种方式输出与输入相关的数字，更小和更近，我们知道我们可以丢弃更大和更远的数字。在输出中出现一个小数字后，该位置之前的更大数字不会对后面的内容产生任何影响。
因此，为了在输出序列减少时限制这些输入范围，我们需要存储 stairs - 原始数组中位置的可能值越来越大的列表。例如，0,2,5,7,2,4 的楼梯是这样构成的：0、0,2、0,2,5、0,2,5,7、0,2、0,2,4.
使用这些边界我们可以确定第二个 2 位置的数字（示例中最后一个位置的旁边）必须在 (2,5] 中，因为 5 是下一个楼梯。如果输入大于 5，则 space 中会输出 5 而不是 2。请注意，如果编码数组中的最后一个数字不是 4，而是 6，我们会提前退出返回0，因为我们知道之前的数字不能大于5。
复杂度为O(n*lg(min(n,m)))。
函数
CombinationsWithReplacement - 从 n 个数中计算 number of combinations with replacements 个大小 k。例如。对于 (3, 2)，它计数 3,3、3,2、3,1、2,2、2,1、1,1，因此 returns 6 等同于choose(n - 1 + k, n - 1).
nextBigger - 在范围内查找下一个更大的元素。例如。对于 4 在子数组 1,2,3,4,5 中它 returns 5，在子数组 1,3 中它 returns 它的参数 Max .
countSpan (lambda) - 计算我们刚刚通过 的跨度可以有多少种不同的组合。考虑 0,2,5,7,2,2,7 的跨度 2,2。
- 当
curr到达最终位置时，curr是7，prev是2,2跨度的最后2 .
- 它计算
prev 跨度的最大和最小可能值。此时楼梯由 2,5,7 组成，然后最大可能值为 5（stair 2,5,7 中的 2 之后的 nextBigger）。在此范围内大于 5 的值将输出 5，而不是 2。
- 它计算跨度的最小值（这是跨度中每个元素的最小值），此时为
prev，（记住此时curr等于7 和 prev 到 2）。我们肯定知道，代替最终的 2 输出，原始输入必须有 7，所以最小值是 7。 （这是 "output goes up" 规则的结果。如果我们有 7,7,2 并且 curr 将是 2 那么前一个跨度的最小值（7,7）将是 8 即 prev + 1.
调整组合数。对于长度为 L 且范围为 n 的跨度（1+max-min），有 种可能性，其中k 是 L 或 L-1 取决于跨度后面的内容。
- 对于后跟更大数字的跨度，例如
2,2,7，k = L - 1因为最后一个位置2,2 跨度的必须是 7（跨度后第一个数字的值）。
- 对于后跟 较小 数字的跨度，例如
7,7,2、k = L 因为
7,7 的最后一个元素没有特殊限制。
最后，它调用CombinationsWithReplacement找出分支（或可能性）的数量，计算新的res部分结果值（我们在模运算中的剩余值做）和 returns 新的 res 值和 max 用于进一步处理。
solution - 遍历给定的编码器输出数组。在主循环中，在跨度中计算跨度长度，并在跨度边界处通过调用 countSpan 更新 res 并可能更新 阶梯 。
- 如果当前跨度包含比前一个更大的数字，则：
- 检查下一个号码的有效性。例如
0,2,5,2,7是无效输入，因为倒数第二个位置不能有7，只有3，或4，或5.
- 它更新了楼梯。当我们只看到
0,2时，楼梯是0,2，但是在下一个5之后，楼梯就变成了0,2,5。
- 如果当前跨度由比前一个更小的数字组成，则：
- 它更新了楼梯。当我们只看到
0,2,5时，我们的楼梯是0,2,5，但是当我们看到0,2,5,2后，楼梯就变成了0,2。
- 在主循环之后，它通过调用
countSpan 和 -1 来计算最后一个跨度，这会触发 "output goes down" 计算分支。
normalizeMod、extendedEuclidInternal、extendedEuclid、invMod - 这些辅助函数有助于处理模运算。
对于楼梯，我使用编码数组的存储空间，因为楼梯的数量永远不会超过当前位置。
#include <algorithm>
#include <cassert>
#include <vector>
#include <tuple>
const int Modulus = 1'000'000'007;
int CombinationsWithReplacement(int n, int k);
template <class It>
auto nextBigger(It begin, It end, int value, int Max) {
auto maxIt = std::upper_bound(begin, end, value);
auto max = Max;
if (maxIt != end) {
max = *maxIt;
}
return max;
}
auto solution(std::vector<int> &B, const int Max) {
auto res = 1;
const auto size = (int)B.size();
auto spanLength = 1;
auto prev = 0;
// Stairs is the list of numbers which could be smaller than number in the next position
const auto stairsBegin = B.begin();
// This includes first entry (zero) into stairs
// We need to include 0 because we can meet another zero later in encoded array
// and we need to be able to find in stairs
auto stairsEnd = stairsBegin + 1;
auto countSpan = [&](int curr) {
const auto max = nextBigger(stairsBegin, stairsEnd, prev, Max);
// At the moment when we switch from the current span to the next span
// prev is the number from previous span and curr from current.
// E.g. 1,1,7, when we move to the third position cur = 7 and prev = 1.
// Observe that, in this case minimum value possible in place of any of 1's can be at least 2=1+1=prev+1.
// But if we consider 7, then we have even more stringent condition for numbers in place of 1, it is 7
const auto min = std::max(prev + 1, curr);
const bool countLast = prev > curr;
const auto branchesCount = CombinationsWithReplacement(max - min + 1, spanLength - (countLast ? 0 : 1));
return std::make_pair(res * (long long)branchesCount % Modulus, max);
};
for (int i = 1; i < size; ++i) {
const auto curr = B[i];
if (curr == prev) {
++spanLength;
}
else {
int max;
std::tie(res, max) = countSpan(curr);
if (prev < curr) {
if (curr > max) {
// 0,1,5,1,7 - invalid because number in the fourth position lies in [2,5]
// and so in the fifth encoded position we can't something bigger than 5
return 0;
}
// It is time to possibly shrink stairs.
// E.g if we had stairs 0,2,4,9,17 and current value is 5,
// then we no more interested in 9 and 17, and we change stairs to 0,2,4,5.
// That's because any number bigger than 9 or 17 also bigger than 5.
const auto s = std::lower_bound(stairsBegin, stairsEnd, curr);
stairsEnd = s;
*stairsEnd++ = curr;
}
else {
assert(curr < prev);
auto it = std::lower_bound(stairsBegin, stairsEnd, curr);
if (it == stairsEnd || *it != curr) {
// 0,5,1 is invalid sequence because original sequence lloks like this 5,>5,>1
// and there is no 1 in any of the two first positions, so
// it can't appear in the third position of the encoded array
return 0;
}
}
spanLength = 1;
}
prev = curr;
}
res = countSpan(-1).first;
return res;
}
template <class T> T normalizeMod(T a, T m) {
if (a < 0) return a + m;
return a;
}
template <class T> std::pair<T, std::pair<T, T>> extendedEuclidInternal(T a, T b) {
T old_x = 1;
T old_y = 0;
T x = 0;
T y = 1;
while (true) {
T q = a / b;
T t = a - b * q;
if (t == 0) {
break;
}
a = b;
b = t;
t = x; x = old_x - x * q; old_x = t;
t = y; y = old_y - y * q; old_y = t;
}
return std::make_pair(b, std::make_pair(x, y));
}
// Returns gcd and Bezout's coefficients
template <class T> std::pair<T, std::pair<T, T>> extendedEuclid(T a, T b) {
if (a > b) {
if (b == 0) return std::make_pair(a, std::make_pair(1, 0));
return extendedEuclidInternal(a, b);
}
else {
if (a == 0) return std::make_pair(b, std::make_pair(0, 1));
auto p = extendedEuclidInternal(b, a);
std::swap(p.second.first, p.second.second);
return p;
}
}
template <class T> T invMod(T a, T m) {
auto p = extendedEuclid(a, m);
assert(p.first == 1);
return normalizeMod(p.second.first, m);
}
int CombinationsWithReplacement(int n, int k) {
int res = 1;
for (long long i = n; i < n + k; ++i) {
res = res * i % Modulus;
}
int denom = 1;
for (long long i = k; i > 0; --i) {
denom = denom * i % Modulus;
}
res = res * (long long)invMod(denom, Modulus) % Modulus;
return res;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// Only the above is needed for the Codility challenge. Below is to run on the command line.
//
// Compile with: gcc -std=gnu++14 -lc++ -lstdc++ array_recovery.cpp
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <string.h>
// Usage: 0 1 2,3, 4 M
// Last arg is M, the max value for an input.
// Remaining args are B (the output of the encoder) separated by commas and/or spaces
// Parentheses and brackets are ignored, so you can use the same input form as Codility's tests: ([1,2,3], M)
int main(int argc, char* argv[]) {
int Max;
std::vector<int> B;
const char* delim = " ,[]()";
if (argc < 2 ) {
printf("Usage: %s M 0 1 2,3, 4... \n", argv[0]);
return 1;
}
for (int i = 1; i < argc; i++) {
char* parse;
parse = strtok(argv[i], delim);
while (parse != NULL)
{
B.push_back(atoi(parse));
parse = strtok (NULL, delim);
}
}
Max = B.back();
B.pop_back();
printf("%d\n", solution(B, Max));
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// Only the above is needed for the Codility challenge. Below is to run on the command line.
//
// Compile with: gcc -std=gnu++14 -lc++ -lstdc++ array_recovery.cpp
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <string.h>
// Usage: M 0 1 2,3, 4
// first arg is M, the max value for an input.
// remaining args are B (the output of the encoder) separated by commas and/or spaces
int main(int argc, char* argv[]) {
int Max;
std::vector<int> B;
const char* delim = " ,";
if (argc < 3 ) {
printf("Usage: %s M 0 1 2,3, 4... \n", argv[0]);
return 1;
}
Max = atoi(argv[1]);
for (int i = 2; i < argc; i++) {
char* parse;
parse = strtok(argv[i], delim);
while (parse != NULL)
{
B.push_back(atoi(parse));
parse = strtok (NULL, delim);
}
}
printf("%d\n", solution(B, Max));
return 0;
}
让我们看一个例子：
Max = 5
Array is
0 1 3 0 1 1 3
1
1 2..5
1 3 4..5
1 3 4..5 1
1 3 4..5 1 2..5
1 3 4..5 1 2..5 >=..2 (sorry, for a cumbersome way of writing)
1 3 4..5 1 3..5 >=..3 4..5
Now count:
1 1 2 1 3 2 which amounts to 12 total.
我想了解如何解决 Codility ArrayRecovery 挑战，但我什至不知道要参考哪个知识分支。是组合学、优化、计算机科学、集合论还是其他？
编辑：
要咨询的知识分支是 constraint programming, particularly constraint propagation. You also need some combinatorics 知道如果你一次从 [1..n[=110= 范围内取 k 个数字]], 限制是没有数字可以比它前面的数字大，结果是
(n+k-1)!/k!(n-1)! 可能的组合
这与一次 k 的 n 事物的 替换 的组合数量相同，它具有数学符号
Peter Norvig 提供了一个很好的例子来说明如何用他的 Sudoku solver.
解决这类问题您可以通过上面的 link 阅读 ArrayRecovery 问题的完整描述。简而言之，有一个 编码器 接受范围为 1 的 整数序列 到某个给定的限制（比如我们的目的是 100 ) 和 对于输入序列的每个元素 输出 最近看到的小于当前输入的整数，或者如果 none 存在则为 0.
input 1, 2, 3, 4 => output 0, 1, 2, 3
input 2, 4, 3 => output 0, 2, 2
完整的任务是，给定输出（以及允许输入的范围），找出有多少可能的输入可以生成它。但在我开始计算之前，我对如何制定方程式没有信心。这就是我寻求帮助的原因。 （当然，如果有解释，也欢迎提供完整的解决方案。）
我只是看看一些可能的输出并想知道。这里有一些示例编码器输出和我能想到的输入，* 表示任何有效输入，> 4 表示任何大于 4 的有效输入。如果需要，输入被称为 A1, A2, A3, ...（基于 1 的索引）
编辑#2
我在这个挑战中遇到的部分问题是我没有为输出手动生成完全正确的可能输入集。我相信下面的设置现在是正确的。如果您想查看我之前的错误，请查看此答案的编辑历史。
output #1: 0, 0, 0, 4
possible inputs: [>= 4, A1 >= * >= 4, 4, > 4]
output #2: 0, 0, 0, 2, 3, 4 # A5 ↴ See more in discussion below
possible inputs: [>= 2, A1 >= * >=2, 2, 3, 4, > 4]
output #3: 0, 0, 0, 4, 3, 1
possible inputs: none # [4, 3, 1, 1 >= * > 4, 4, > 1] but there is no number 1 >= * > 4
与第一个输入序列相比，第二个输入序列的约束非常严格，只是增加了 2 个输出。第三个序列被限制得不可能。
但是示例 #2 中 A5 的一组约束有点难以表达。当然A5 > O5，这是对所有输入的基本约束。但是任何 > A4 和 O5 之后的输出都必须出现在 A4 之后的输入中，因此 A5 必须是 A5 之后也 > A4 的数字集中的一个元素。由于只有 1 个这样的数字 (A6 == 4)，因此必须是 A5，但如果后面有更长的数字串，它会变得更复杂。 （编者按：其实不是。）
随着输出集越来越长，我担心这些约束会变得越来越复杂，越来越难以正确处理。我想不出有任何数据结构可以有效地表示这些数据，从而有效地计算出可能的组合数量。我也不太明白如何通过算法将约束集添加在一起。
这是我目前看到的任何给定 An
的约束- An > On
- An <= min（从 O1 到 n-1[= 的其他可能数字集116=] > On)。如何定义大于On的可能数集合？
- 在输入 中最近出现 On 之后大于 On 的数字
- An >= max(从 O1 到 n-1[= 的其他可能数字集116=] < On)。如何定义小于On的可能数集合？
- 实际上这个集合是空的，因为根据定义，On 是前一个输入序列中最大的可能 数。 （这并不是说它严格来说是前一个输入序列中最大的数字。）
- 输入中最后一次出现之前出现的任何小于 On 的数字都不符合条件，因为 "nearest" 规则。由于 "nearest" 规则和可传递的 属性：如果 Ai < On 和 Aj < Ai 那么 Aj < On
- 然后是集合论：
- An 必须是 On+1 到 Om，其中 m 是满足 Om < On 的最小 m > n。在这样的 Om 之后并且大于 Om （An 是）的任何输出都必须出现在 Am. 之后或之后
- 如果一个元素出现在输出中但没有出现在输入中与输出的其余部分一致的位置，则该元素未被解释。显然我需要比这更好的定义，以便编写代码和算法来计算它。
似乎某种集合论 and/or 组合学或线性代数可能有助于计算可能的序列数量，这些序列将解释所有未解释的输出并满足其他约束条件. （编者按：其实，事情永远不会变得那么复杂。）
这是一个主意。构造输出的一种已知方法是使用堆栈。我们在元素大于或等于时弹出它，然后输出较小的元素（如果存在），然后将较大的元素压入堆栈。现在，如果我们尝试从输出向后执行此操作怎么办？
首先我们将使用 c∅dility 示例演示堆栈方法。
[2, 5, 3, 7, 9, 6]
2: output 0, stack [2]
5: output 2, stack [2,5]
3: pop 5, output, 2, stack [2,3]
7: output 3, stack [2,3,7]
... etc.
Final output: [0, 2, 2, 3, 7, 3]
现在让我们尝试重建！我们将使用 stack 作为假想堆栈和重构输入：
(Input: [2, 5, 3, 7, 9, 6])
Output: [0, 2, 2, 3, 7, 3]
* Something >3 that reached 3 in the stack
stack = [3, 3 < *]
* Something >7 that reached 7 in the stack
but both of those would've popped before 3
stack = [3, 7, 7 < x, 3 < * <= x]
* Something >3, 7 qualifies
stack = [3, 7, 7 < x, 3 < * <= x]
* Something >2, 3 qualifies
stack = [2, 3, 7, 7 < x, 3 < * <= x]
* Something >2 and >=3 since 3 reached 2
stack = [2, 2 < *, 3, 7, 7 < x, 3 < * <= x]
让我们试试你的例子：
示例 1：
[0, 0, 0, 2, 3, 4]
* Something >4
stack = [4, 4 < *]
* Something >3, 4 qualifies
stack = [3, 4, 4 < *]
* Something >2, 3 qualifies
stack = [2, 3, 4, 4 < *]
* The rest is non-increasing with lowerbound 2
stack = [y >= x, x >= 2, 2, 3, 4, >4]
示例 2：
[0, 0, 0, 4]
* Something >4
stack [4, 4 < *]
* Non-increasing
stack = [z >= y, y >= 4, 4, 4 < *]
计算组合的数量是通过将所有部分的可能性相乘来实现的。一个部分是一个有界的单细胞；或一个或多个单元格的绑定、非增加子数组。为了计算后者，我们使用多项选择二项式 (n + k - 1) choose (k - 1)。考虑到我们可以将 3 单元格的绑定非增加序列的单元格之间的差异表示为：
(ub - cell_3) + (cell_3 - cell_2) + (cell_2 - cell_1) + (cell_1 - lb) = ub - lb
那么将 ub - lb 分配到 (x + 1) 个单元格的方法数是
(n + k - 1) choose (k - 1)
or
(ub - lb + x) choose x
For example, the number of non-increasing sequences between
(3,4) in two cells is (4 - 3 + 2) choose 2 = 3: [3,3] [4,3] [4,4]
And the number of non-increasing sequences between
(3,4) in three cells is (4 - 3 + 3) choose 3 = 4: [3,3,3] [4,3,3] [4,4,3] [4,4,4]
（解释归因于 Brian M. Scott。）
粗略的JavaScript草图（代码不可靠，只是为了说明编码。编码器列出了[lower_bound，upper_bound]，或者一个非递增序列作为[non_inc, 长度, lower_bound, upper_bound]):
function f(A, M){
console.log(JSON.stringify(A), M);
let i = A.length - 1;
let last = A[i];
let s = [[last,last]];
if (A[i-1] == last){
let d = 1;
s.splice(1,0,['non_inc',d++,last,M]);
while (i > 0 && A[i-1] == last){
s.splice(1,0,['non_inc',d++,last,M]);
i--
}
} else {
s.push([last+1,M]);
i--;
}
if (i == 0)
s.splice(0,1);
for (; i>0; i--){
let x = A[i];
if (x < s[0][0])
s = [[x,x]].concat(s);
if (x > s[0][0]){
let [l, _l] = s[0];
let [lb, ub] = s[1];
s[0] = [x+1, M];
s[1] = [lb, x];
s = [[l,_l], [x,x]].concat(s);
}
if (x == s[0][0]){
let [l,_l] = s[0];
let [lb, ub] = s[1];
let d = 1;
s.splice(0,1);
while (i > 0 && A[i-1] == x){
s =
[['non_inc', d++, lb, M]].concat(s);
i--;
}
if (i > 0)
s = [[l,_l]].concat(s);
}
}
// dirty fix
if (s[0][0] == 0)
s.splice(0,1);
return s;
}
var a = [2, 5, 3, 7, 9, 6]
var b = [0, 2, 2, 3, 7, 3]
console.log(JSON.stringify(a));
console.log(JSON.stringify(f(b,10)));
b = [0,0,0,4]
console.log(JSON.stringify(f(b,10)));
b = [0,2,0,0,0,4]
console.log(JSON.stringify(f(b,10)));
b = [0,0,0,2,3,4]
console.log(JSON.stringify(f(b,10)));
b = [0,2,2]
console.log(JSON.stringify(f(b,4)));
b = [0,3,5,6]
console.log(JSON.stringify(f(b,10)));
b = [0,0,3,0]
console.log(JSON.stringify(f(b,10)));
下面的代码通过了 Codility 的所有测试。 OP 添加了一个 main 函数以在命令行上使用它。
约束并不像 OP 想象的那么复杂。特别是，在任何情况下，您都不需要添加限制，即输入是输出中其他地方出现的某些特定整数集的元素。每个输入位置都有明确定义的最小值和最大值。
该规则的唯一复杂之处在于，有时最大值是 "the value of the previous input"，并且输入本身有一个范围。但即便如此，所有类似的值都是连续的并且具有相同的范围，因此可以使用基本组合学计算可能性的数量，并且这些输入作为一个组独立于其他输入（仅用于设置范围） , 因此该组的可能性可以通过简单的乘法与其他输入位置的可能性相结合。
算法概述
该算法在每个 span 之后单次通过输出数组更新输入数组的可能数量，这就是我所说的输出中数字的重复。 （您可能会说每个元素都相同的输出的最大子序列。）例如，对于输出 0,1,1,2，我们有三个跨度：0、1,1 和 2。当新的跨度开始时，将计算前一个跨度的可能性数。
这个决定是基于一些观察：
- 对于长度大于1的spans，输入的最小值 允许在第一个位置是输入的任何值 在第二个位置。计算一个可能性的数量 跨度是简单的组合，但标准公式 需要知道数字的范围和跨度的长度。
- 每次值
输出变化（和一个新的跨度存在），强烈限制了前一个跨度的值：
- 当输出上升时，唯一可能的原因是之前的输入是新的更高输出的值，而新的更高输出的位置对应的输入更高。
- 当输出下降时，会建立新的约束，但这些约束有点难以表达。该算法存储 stairs（见下文）以量化输出下降时施加的约束
此处的目的是限制每个 span 的可能值范围。一旦我们准确地做到这一点，计算组合的数量就很简单了。
因为编码器回溯寻找以两种方式输出与输入相关的数字，更小和更近，我们知道我们可以丢弃更大和更远的数字。在输出中出现一个小数字后，该位置之前的更大数字不会对后面的内容产生任何影响。
因此，为了在输出序列减少时限制这些输入范围，我们需要存储 stairs - 原始数组中位置的可能值越来越大的列表。例如，0,2,5,7,2,4 的楼梯是这样构成的：0、0,2、0,2,5、0,2,5,7、0,2、0,2,4.
使用这些边界我们可以确定第二个 2 位置的数字（示例中最后一个位置的旁边）必须在 (2,5] 中，因为 5 是下一个楼梯。如果输入大于 5，则 space 中会输出 5 而不是 2。请注意，如果编码数组中的最后一个数字不是 4，而是 6，我们会提前退出返回0，因为我们知道之前的数字不能大于5。
复杂度为O(n*lg(min(n,m)))。
函数
CombinationsWithReplacement- 从n个数中计算 number of combinations with replacements 个大小k。例如。对于(3, 2)，它计数3,3、3,2、3,1、2,2、2,1、1,1，因此 returns6等同于choose(n - 1 + k, n - 1).nextBigger- 在范围内查找下一个更大的元素。例如。对于4在子数组1,2,3,4,5中它 returns5，在子数组1,3中它 returns 它的参数Max.countSpan(lambda) - 计算我们刚刚通过 的跨度可以有多少种不同的组合。考虑0,2,5,7,2,2,7的跨度2,2。- 当
curr到达最终位置时，curr是7，prev是2,2跨度的最后2. - 它计算
prev跨度的最大和最小可能值。此时楼梯由2,5,7组成，然后最大可能值为5（stair 2,5,7中的2之后的nextBigger）。在此范围内大于5的值将输出5，而不是2。 - 它计算跨度的最小值（这是跨度中每个元素的最小值），此时为
prev，（记住此时curr等于7和prev到2）。我们肯定知道，代替最终的2输出，原始输入必须有7，所以最小值是7。 （这是 "output goes up" 规则的结果。如果我们有7,7,2并且curr将是2那么前一个跨度的最小值（7,7）将是8即prev + 1. 调整组合数。对于长度为 L 且范围为 n 的跨度（1+max-min），有
- 对于后跟更大数字的跨度，例如
2,2,7，k = L - 1因为最后一个位置2,2跨度的必须是7（跨度后第一个数字的值）。 - 对于后跟 较小 数字的跨度，例如
7,7,2、k = L 因为7,7的最后一个元素没有特殊限制。
- 对于后跟更大数字的跨度，例如
最后，它调用
CombinationsWithReplacement找出分支（或可能性）的数量，计算新的res部分结果值（我们在模运算中的剩余值做）和 returns 新的res值和max用于进一步处理。
- 当
solution- 遍历给定的编码器输出数组。在主循环中，在跨度中计算跨度长度，并在跨度边界处通过调用countSpan更新res并可能更新 阶梯 。- 如果当前跨度包含比前一个更大的数字，则：
- 检查下一个号码的有效性。例如
0,2,5,2,7是无效输入，因为倒数第二个位置不能有7，只有3，或4，或5. - 它更新了楼梯。当我们只看到
0,2时，楼梯是0,2，但是在下一个5之后，楼梯就变成了0,2,5。
- 检查下一个号码的有效性。例如
- 如果当前跨度由比前一个更小的数字组成，则：
- 它更新了楼梯。当我们只看到
0,2,5时，我们的楼梯是0,2,5，但是当我们看到0,2,5,2后，楼梯就变成了0,2。
- 它更新了楼梯。当我们只看到
- 在主循环之后，它通过调用
countSpan和-1来计算最后一个跨度，这会触发 "output goes down" 计算分支。
- 如果当前跨度包含比前一个更大的数字，则：
normalizeMod、extendedEuclidInternal、extendedEuclid、invMod- 这些辅助函数有助于处理模运算。
对于楼梯，我使用编码数组的存储空间，因为楼梯的数量永远不会超过当前位置。
#include <algorithm>
#include <cassert>
#include <vector>
#include <tuple>
const int Modulus = 1'000'000'007;
int CombinationsWithReplacement(int n, int k);
template <class It>
auto nextBigger(It begin, It end, int value, int Max) {
auto maxIt = std::upper_bound(begin, end, value);
auto max = Max;
if (maxIt != end) {
max = *maxIt;
}
return max;
}
auto solution(std::vector<int> &B, const int Max) {
auto res = 1;
const auto size = (int)B.size();
auto spanLength = 1;
auto prev = 0;
// Stairs is the list of numbers which could be smaller than number in the next position
const auto stairsBegin = B.begin();
// This includes first entry (zero) into stairs
// We need to include 0 because we can meet another zero later in encoded array
// and we need to be able to find in stairs
auto stairsEnd = stairsBegin + 1;
auto countSpan = [&](int curr) {
const auto max = nextBigger(stairsBegin, stairsEnd, prev, Max);
// At the moment when we switch from the current span to the next span
// prev is the number from previous span and curr from current.
// E.g. 1,1,7, when we move to the third position cur = 7 and prev = 1.
// Observe that, in this case minimum value possible in place of any of 1's can be at least 2=1+1=prev+1.
// But if we consider 7, then we have even more stringent condition for numbers in place of 1, it is 7
const auto min = std::max(prev + 1, curr);
const bool countLast = prev > curr;
const auto branchesCount = CombinationsWithReplacement(max - min + 1, spanLength - (countLast ? 0 : 1));
return std::make_pair(res * (long long)branchesCount % Modulus, max);
};
for (int i = 1; i < size; ++i) {
const auto curr = B[i];
if (curr == prev) {
++spanLength;
}
else {
int max;
std::tie(res, max) = countSpan(curr);
if (prev < curr) {
if (curr > max) {
// 0,1,5,1,7 - invalid because number in the fourth position lies in [2,5]
// and so in the fifth encoded position we can't something bigger than 5
return 0;
}
// It is time to possibly shrink stairs.
// E.g if we had stairs 0,2,4,9,17 and current value is 5,
// then we no more interested in 9 and 17, and we change stairs to 0,2,4,5.
// That's because any number bigger than 9 or 17 also bigger than 5.
const auto s = std::lower_bound(stairsBegin, stairsEnd, curr);
stairsEnd = s;
*stairsEnd++ = curr;
}
else {
assert(curr < prev);
auto it = std::lower_bound(stairsBegin, stairsEnd, curr);
if (it == stairsEnd || *it != curr) {
// 0,5,1 is invalid sequence because original sequence lloks like this 5,>5,>1
// and there is no 1 in any of the two first positions, so
// it can't appear in the third position of the encoded array
return 0;
}
}
spanLength = 1;
}
prev = curr;
}
res = countSpan(-1).first;
return res;
}
template <class T> T normalizeMod(T a, T m) {
if (a < 0) return a + m;
return a;
}
template <class T> std::pair<T, std::pair<T, T>> extendedEuclidInternal(T a, T b) {
T old_x = 1;
T old_y = 0;
T x = 0;
T y = 1;
while (true) {
T q = a / b;
T t = a - b * q;
if (t == 0) {
break;
}
a = b;
b = t;
t = x; x = old_x - x * q; old_x = t;
t = y; y = old_y - y * q; old_y = t;
}
return std::make_pair(b, std::make_pair(x, y));
}
// Returns gcd and Bezout's coefficients
template <class T> std::pair<T, std::pair<T, T>> extendedEuclid(T a, T b) {
if (a > b) {
if (b == 0) return std::make_pair(a, std::make_pair(1, 0));
return extendedEuclidInternal(a, b);
}
else {
if (a == 0) return std::make_pair(b, std::make_pair(0, 1));
auto p = extendedEuclidInternal(b, a);
std::swap(p.second.first, p.second.second);
return p;
}
}
template <class T> T invMod(T a, T m) {
auto p = extendedEuclid(a, m);
assert(p.first == 1);
return normalizeMod(p.second.first, m);
}
int CombinationsWithReplacement(int n, int k) {
int res = 1;
for (long long i = n; i < n + k; ++i) {
res = res * i % Modulus;
}
int denom = 1;
for (long long i = k; i > 0; --i) {
denom = denom * i % Modulus;
}
res = res * (long long)invMod(denom, Modulus) % Modulus;
return res;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// Only the above is needed for the Codility challenge. Below is to run on the command line.
//
// Compile with: gcc -std=gnu++14 -lc++ -lstdc++ array_recovery.cpp
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <string.h>
// Usage: 0 1 2,3, 4 M
// Last arg is M, the max value for an input.
// Remaining args are B (the output of the encoder) separated by commas and/or spaces
// Parentheses and brackets are ignored, so you can use the same input form as Codility's tests: ([1,2,3], M)
int main(int argc, char* argv[]) {
int Max;
std::vector<int> B;
const char* delim = " ,[]()";
if (argc < 2 ) {
printf("Usage: %s M 0 1 2,3, 4... \n", argv[0]);
return 1;
}
for (int i = 1; i < argc; i++) {
char* parse;
parse = strtok(argv[i], delim);
while (parse != NULL)
{
B.push_back(atoi(parse));
parse = strtok (NULL, delim);
}
}
Max = B.back();
B.pop_back();
printf("%d\n", solution(B, Max));
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// Only the above is needed for the Codility challenge. Below is to run on the command line.
//
// Compile with: gcc -std=gnu++14 -lc++ -lstdc++ array_recovery.cpp
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <string.h>
// Usage: M 0 1 2,3, 4
// first arg is M, the max value for an input.
// remaining args are B (the output of the encoder) separated by commas and/or spaces
int main(int argc, char* argv[]) {
int Max;
std::vector<int> B;
const char* delim = " ,";
if (argc < 3 ) {
printf("Usage: %s M 0 1 2,3, 4... \n", argv[0]);
return 1;
}
Max = atoi(argv[1]);
for (int i = 2; i < argc; i++) {
char* parse;
parse = strtok(argv[i], delim);
while (parse != NULL)
{
B.push_back(atoi(parse));
parse = strtok (NULL, delim);
}
}
printf("%d\n", solution(B, Max));
return 0;
}
让我们看一个例子：
Max = 5
Array is
0 1 3 0 1 1 3
1
1 2..5
1 3 4..5
1 3 4..5 1
1 3 4..5 1 2..5
1 3 4..5 1 2..5 >=..2(sorry, for a cumbersome way of writing)
1 3 4..5 1 3..5 >=..3 4..5
Now count:
1 1 2 1 3 2which amounts to12total.