时间戳

首页 > 解决方案 > 从输出重构编码器的输入

algorithm - 从输出重构编码器的输入

问题描述

我想了解如何解决 Codility ArrayRecovery挑战，但我什至不知道要咨询哪个知识分支。是组合学、优化、计算机科学、集合论还是其他？

编辑： 要参考的知识分支是约束编程，特别是约束传播。您还需要一些组合学才能知道，如果您一次从范围 [1.. n ] 中取k个数字，并且限制没有数字可以大于它之前的数字，则结果为 (n+k -1)!/k!(n-1)! 可能的组合，它与一次替换n 个事物的组合数相同，具有数学符号。您可以在此处了解为什么会这样。nCRk

Peter Norvig 提供了一个很好的例子来说明如何用他的数独求解器来解决这类问题。

您可以通过上面的链接阅读 ArrayRecovery 问题的完整描述。简短的故事是，有一个编码器接受范围为 1的整数序列，直到某个给定的限制（例如 100 用于我们的目的），并且对于输入序列的每个元素，输出最近看到的小于当前输入，如果不存在，则为 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 必须是它，但如果后面有更长的数字串，它会变得更加复杂。（编者注：实际上并没有。）

随着输出集变得越来越长，我担心这些约束会变得更加复杂且难以正确处理。我想不出任何数据结构可以有效地表示这些，从而有效地计算可能组合的数量。我也不太明白如何通过算法将约束集添加在一起。

以下是我目前看到的任何给定 A n的约束

似乎某种集合论和/或组合学或线性代数可能有助于确定可能的序列数量，这些序列将解释所有未解释的输出并适合其他约束。（编者注：实际上，事情从来没有变得那么复杂。）

标签： algorithmdata-structurescombinatoricsconstraint-programming

解决方案

下面的代码通过了 Codility 的所有测试。OP 添加了一个main函数以在命令行上使用它。

约束并不像 OP 认为的那么复杂。特别是，永远不会出现需要添加限制，即输入是输出中其他地方看到的某些特定整数集合的元素。每个输入位置都有明确定义的最小值和最大值。

该规则的唯一复杂之处在于，有时最大值是“前一个输入的值”，并且该输入本身有一个范围。但即便如此，所有类似的值都是连续的并且具有相同的范围，因此可以使用基本组合计算可能性的数量，并且这些输入作为一个组独立于其他输入（仅用于设置范围） ，因此该组的可能性可以通过简单的乘法与其他输入位置的可能性相结合。

算法概述

该算法在每个span之后通过输出数组更新输入数组的可能数量，这就是我所说的输出中数字的重复。（您可能会说每个元素都相同的输出的最大子序列。）例如，对于输出，0,1,1,2我们有三个跨度0：1,1和2。当一个新的跨度开始时，计算前一个跨度的可能性数量。

这个决定是基于一些观察：

  • 对于长度超过 1 的跨度，第一个位置允许的输入的最小值是第二个位置的输入值。计算跨度的可能性数量是简单的组合学，但标准公式需要知道数字的范围和跨度的长度。
  • 每次输出的值发生变化（以及新的跨度存在）时，都会强烈限制前一个跨度的值：
    1. 当输出上升时，唯一可能的原因是先前的输入是新的更高输出的值，而对应于新的更高输出位置的输入甚至更高。
    2. 当输出下降时，会建立新的约束，但这些约束有点难以表达。该算法存储楼梯（见下文），以便量化输出下降时施加的约束

这里的目的是限制每个span的可能值范围。一旦我们准确地做到了这一点，计算组合的数量就很简单了。

因为编码器回溯希望以两种方式输出与输入相关的数字，更小和更接近，我们知道我们可以抛出更大和更远的数字。在输出中出现少量数字后，该位置之前的较大数字不会对后面的内容产生任何影响。

因此，当输出序列减少时，为了限制这些输入范围，我们需要存储楼梯——原始数组中位置的可能值越来越大的列表。例如，对于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，则会在该空间中输出 5 而不是 2。请注意，如果编码数组中的最后一个数字不是4，而是6，我们将退出提前返回0，因为我们知道前一个数字不能大于5。

复杂度是O(n*lg(min(n,m)))。

功能

  • CombinationsWithReplacement-从数字中计算大小替换的组合数量。例如，它计数, , , , , , 所以返回它与 相同。kn(3, 2)3,33,23,12,22,11,16choose(n - 1 + k, n - 1)

  • nextBigger- 在一个范围内找到下一个更大的元素。例如，4在子数组中1,2,3,4,5它返回5，在子数组中1,3它返回它的参数Max。

  • countSpan(lambda) - 计算我们刚刚通过的跨度可以有多少种不同的组合。考虑跨度2,2。0,2,5,7,2,2,7

    1. 当curr到达最终位置时，curr是7并且prev是跨度2的最终位置。2,2
    2. 它计算prev跨度的最大和最小可能值。此时楼梯由2,5,7最大可能值组成5（在nextBigger之后）。大于此跨度的值将输出 a ，而不是 a 。2stair 2,5,7552
    3. 它计算跨度的最小值（这是跨度中每个元素的最小值），即prev此时，（记住curr此时等于和7）。我们肯定知道，原始输入必须代替最终输出，所以最小值是。（这是“输出上升”规则的结果。如果我们有并且将会是前一个跨度的最小值（the ）将是which is 。prev22777,7,2curr27,78prev + 1

    4. 它调整组合的数量。对于具有n 个可能性（1+max-min）范围的长度为L的跨度，存在多种可能性，其中k是L或L-1，具体取决于跨度之后的内容。k个组合替换n个

      • 对于后跟较大数字的跨度，例如2,2,7，k = L - 1因为跨度的最后位置2,2必须是7（跨度之后的第一个数字的值）。
      • 对于后跟较小数字的跨度，例如7,7,2，k = L，因为 的最后一个元素7,7没有特殊约束。

    5. 最后，它调用CombinationsWithReplacement找出分支（或可能性）的数量，计算新的res部分结果值（我们正在做的模运算中的剩余值），并返回新res值并max进行进一步处理。

  • solution- 迭代给定的编码器输出数组。在主循环中，在跨度中，它计算跨度长度，并在跨度边界处res通过调用countSpan更新并可能更新楼梯。

    • 如果当前跨度包含比前一个更大的数字，则：
      1. 检查下一个号码的有效性。例如0,2,5,2,7，无效输入，因为不能7在倒数第二个位置，只有3、 或4、 或5。
      2. 它更新了楼梯。当我们只看到0,2，楼梯是0,2，但经过下5，楼梯就变成了0,2,5。
    • 如果当前跨度包含比前一个更小的数字，则：
      1. 它更新楼梯。当我们只看到0,2,5楼梯时，我们的楼梯是0,2,5，但在我们看到0,2,5,2楼梯之后就变成了0,2。
    • countSpan在主循环之后，它通过调用-1触发“输出下降”计算分支来计算最后一个跨度。
  • 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
数组是
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（对不起，写起来很麻烦）
1 3 4..5 1 3..5 >=..3 4..5
现在 count:
1 1 2 1 3 2等于12总数。

推荐阅读