这个谜题有容易实现的解决方案吗？

Question

我有一个脑筋急转弯，在我们大学的算法和谜题聚会上读到，内容如下：

有一所学校，奖励那些在给定时间内只迟到一次且不连续缺席三天以上的学生。对于给定时间段，我们可以构建多少个重复出现（或缺席）的可能排列，以授予学生奖项？假设每天仅有“准时”，“迟到”或“缺席”三种状态，不必担心具体课程。例如：对于为期三天的时间段，我们可以创建19个这样的排列，以授予奖项。

我昨天已经在math.SE上发布了它，因为我想知道是否有一些现成的公式可以推导来解决它，但结果证明没有，所有的变换都相当复杂。

因此，我在这里问 - 您将如何用算法解决这个问题？我试图缩小可能性空间，但过了一会儿，考虑到所有可能的重复排列就变得太多了，而且算法开始变得非常复杂，而我认为应该有一种易于实现的方法来解决它，特别是因为我们在聚会上交换的大多数谜题都是这样的。

- Straightfw

---

你能给我数学站点的对话链接吗？这样我就不会重复已经在那里说过的话了。 - A. Abramov

http://math.stackexchange.com/questions/1279610/a-seemingly-easy-combinatorics-brain-teaser - Jay Kominek

Answer 1

这个问题呼之欲出地需要递归（和/或动态规划）！

假设我们试图解决一个略微一般化的问题：

我们如果学生迟到不超过L次，且未缺席连续A天，则给予奖励。

现在我们想要计算在n天时间段内这种情况的可能性总数。将其命名为方法P(L, A, n)。

现在尝试基于三种情况建立递归，以解决该期间的第一天。

1）如果学生第一天准时到达，则该数量就是 P(L, A, n-1)。

2）如果学生第一天迟到了，则该数量就是 P(L-1, A, n-1)。

3）如果学生第一天缺席，则该数量就是 P(L, A-1, n-1)。

这给我们提供了以下递归公式：

P(L, A, n) = P(L, A, n-1) + P(L-1, A, n-1) + P(L, A-1, n-1)

你可以通过记忆化递归或查找表来实现它。

请注意基本情况是 P(0, *, *), P(*, 0, *) 和 P(*, *, 0)，并且可以通过简单的数学公式计算得出。

下面是一个快速的 Python 代码，采用记忆化+递归来演示：

import math

def binom(n, r):
  return math.factorial(n)/(math.factorial(r)*math.factorial(n-r))

# The memoization table.
table = {}

def P(L, A, n):

  if L == 0:
    # Only ontime or absent.
    # More absents than period.
    if A > n:
      return 2**n
    # 2^n total possibilities.
    # of that n-A+1 are non-rewarding.
    return 2**n - (n - A + 1)

  if A == 0:
    # Only Late or ontime.
    # need fewer than L+1 late.
    # This is n choose 0 + n choose 1 + ... + n choose L
    total = 0
    for l in xrange(0, min(L,n)):
      total += binom(n, l)
    return total

  if n == 0:
    return 1

  if (L, A, n) in table:
    return table[(L, A, n)]

  result = P(L, A, n-1) + P(L-1, A, n-1) + P(L, A-1, n-1)
  table[(L, A, n)] = result
  return result

print P(1, 3, 3)

输出结果为19。

- Programmer Person

Answer 2

这里是一个简化版的Python 3代码，实现了@ProgrammerPerson回答中的递归功能：

from functools import lru_cache

def count_variants(max_late, base_absent, period_length):
    """
    max_late – maximum allowed number of days the student can be late;
    base_absent – the number of consecutive days the student can be absent;
    period_length – days in a period."""

    @lru_cache(max_late * base_absent * period_length)
    def count(late, absent, days):
        if late < 0: return 0
        if absent < 0: return 0
        if days == 0: return 1
        return (count(late, base_absent, days-1) +   # Student is on time. Absent reset.
                count(late-1, base_absent, days-1) + # Student is late. Absent reset.
                count(late, absent-1, days-1))       # Student is absent.
    return count(max_late, base_absent, period_length)

运行示例：

In [2]: count_variants(1, 2, 3)
Out[2]: 19

- Kolmar

---

你的基本情况比我的简单得多。我不确定它是否有效，所以我手动编写了它！给你加一分。 - Programmer Person

Answer 3

令S(n)为长度为n的字符串中没有3个连续1的数量。

任何这样的字符串（长度至少为3）以“0”、“01”或“011”结尾（并且在去掉后缀后，任何没有三个连续1的字符串都可以出现）。

因此，对于n > 2，S(n) = S(n-1) + S(n-2) + S(n-3)，且S(0)=1，S(1)=2，S(2)=4。

如果您在第i天有一个晚到，则您有S(i)种方法来安排缺席的天数，在之前，而有S(n-i-1)种方法来安排缺席的天数，在之后。

因此，原问题的解决方案是S(n) + sum(S(i)*S(n-i-1) | i = 0...n-1)。

我们可以像这样迭代计算解决方案：

def ways(n):
    S = [1, 2, 4] + [0] * (n-2)
    for i in xrange(3, n+1):
        S[i] = S[i-1] + S[i-2] + S[i-3]
    return S[n] + sum(S[i] * S[n-i-1] for i in xrange(n))

for i in xrange(1, 20):
    print i, ways(i)

输出：

1 3
2 8
3 19
4 43
5 94
6 200
7 418
8 861
9 1753
10 3536
11 7077
12 14071
13 27820
14 54736
15 107236
16 209305
17 407167
18 789720
19 1527607

- Paul Hankin

---

哇，这是一个非常好的解决方案！不过我有一个问题——为什么 S(n) = S(n-1) + S(n-2) + S(n-3)？我的意思是，它给出了长度为 n-3 的字符串数量，但我们仍然可以用多种方式排列它们。它如何考虑到这一点呢？ - Straightfw

由于前面的观察，@Straightfw。或者参见Sedgewick和Flageolet的《算法分析》中的定理8.2。 - Paul Hankin