满足给定约束的有效序列数

你在这里有一个图搜索问题，可以使用回溯搜索来解决，并且可以使用记忆使运行得更快。

定义状态

按照问题中的规则，状态是元组，其中元组中的第一个值是序列中的当前数字和前一个数字，元组中的第二个值是序列的长度，因为一个数字的出现可以间隔为或更多。a_na_{n-1}2

此外，禁止状态是两个数字不是共质数的状态，这意味着

number_set = [1, 2, 3, 4, 5, 6]

长度为 2 的状态是有效状态，但禁止集除外，该状态为：

forbidden_tuples = {(2,4), (2,6), (4,6), (3,6), (4,2), (6,2), (6,4), (6,3)}

示例：处于状态 （2,3），所需序列长度为 5。在这种情况下，以下数字不能是 2,3（保持至少 2 的距离）或 6（保持相邻数字的共质数），因此总共有你随后的状态：((2,3), 5)

1. ((3,1), 4)
2. ((3,4), 4)
3. ((3,5), 4)

构建解决方案

我将提供的解决方案是图形的递归 DFE，并带有用于时间优化的记忆。解决方案如下：

import itertools

def count_seq(N, start_state=None, memoization=None):
    """
    :param N:
    :param start_state
    :param memoization
    :return: Rules:
    1. a_i in {1,2,3,4,5,6}
    2. Two adjacent numbers should be coprime. For e.g. 2,4,.. sequence is not allowed ( for the set {1,2,3,4,5,6} this means that (2,6),(2,4),(3,6),(4,6) are forbidden
    3. repetitions with a distance >= 2

    State are ordered as a 2 item tuple to remember the history: (a_{n-1} , a_n)
    """
    if N == 1:
        return 6
    if memoization is None:
        memoization = {}
    count = 0
    state_set = set()  # Pending states which have not been explored yet
    number_set = [1, 2, 3, 4, 5, 6]
    forbidden_tuples = {(2,4), (2,6), (4,6), (3,6), (4,2), (6,2), (6,4), (6,3)}
    if start_state is None: # Getting initial states
        for subset in itertools.permutations(number_set, 2):
            if subset in forbidden_tuples:
                pass
            else:
                state_set.add((subset, N))
    else:  # checking all possible next states and appending to queue with 1 less length
        for ii in number_set:
            if ii in start_state or (ii, start_state[-1]) in forbidden_tuples:
                pass
            else:
                state_set.add(((start_state[1:] + tuple([ii])), N-1))
    # for each possible next state
    for state in state_set:
        if state[1] <= 2:
            count += 1
        elif state in memoization:  # checking if we computed this already
            count += memoization[state]
        else:  #we did not compute this, doing the computation
            memoization[state] = count_seq(state[1], state[0], memoization)
            count +=  memoization[state]

    return count

Expleation

如果所需的长度为 1，则为 6，因为任何一个数字都可以位于第 1 个位置。

1. 我们查看开始状态是否为我们假设这是初始调用，因此我们创建了长度为 2 的所有可能的无禁止排列。否则，我们将创建一组所有可能的下一个状态。None

2. 对于每个可能的下一个状态，我们检查：

   2.1. 如果所需的长度为 2：我们将计数增加 1，因为这是一个有效状态

   2.2. 如果长度大于 2，我们检查我们之前是否已经在字典中计算过这个状态。如果我们这样做了，我们从字典中提取计数值并使用它，否则我们以递归方式调用该函数，并具有起始状态和所需的序列长度。memoization

定时

在禁用记忆的情况下运行此函数时，我们得到：N=200

%timeit count_seq_slow(200)
199 ms ± 9.63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit count_seq(200)
13.6 ms ± 833 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

当增加到时，我们得到：N=2000

%timeit count_seq_slow(2000)
3.54 s ± 374 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit count_seq(2000)
147 ms ± 7.02 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

我们可以利用这样一个事实，即只有 6 个可能的数字可用于构造数字。

1. 考虑一个查找表，它基本上是 。dp[i][j][k]count of i-digit numbers with the i-th digit as j, (i-1)th digit as k
2. 为每个数字创建所有有效互质数的映射。类似的东西{2: [1,3,5], 3: [1,2,4,5], 6: [1,5]}...
3. 基本情况：、、dp[0] = 0 for all j,kdp[1] = 0 for all j,kdp[2][j][k] = 1 if gcd(j,k)==1 and j!=k
4. 现在填满桌子应该相对简单。

for i in range 2 to n:
for j in range 1 to 6:
for k in range 1 to 6
if j and k are not coprime, dp[i][j][k] = 0 
else, dp[i][j][k] = summation(dp[i-1][k][l]) where l is in range [1,6] AND l!=j and j!=k
# this ensures a min gap of 3 and maintains co-primality of adjacent numbers

5. 最终答案 =sum(dp[N][1..6])

这具有 ~ 的时空复杂度。O(N*6*6)O(N)

编辑：@KellyBundy很好心地添加了一个 Python 实现;更正了它（以及我回答中的一个小缺陷）并在此处添加：

def count_seq(N):
  A = range(1, 7)
  dp = [[[None] * 7 for _ in range(7)] for _ in range(N+1)]
  for j in A:
    for k in A:
      dp[0][j][k] = 0
      dp[1][j][k] = 0
      dp[2][j][k] = int(gcd(j,k)==1 and j!=k)
  for i in range(3, N+1):
    for j in A:
      for k in A:
        if gcd(j, k) != 1:
          dp[i][j][k] = 0 
        else:
          dp[i][j][k] = sum(dp[i-1][k][l] for l in A if (l!=j and j!=k))
  return sum(dp[N][j][k] for j in A for k in A)

N = 100
print(count_seq(N))

设长度为 n 的有效序列数，使得如果 d1、d2 出现在前面，则该序列仍然有效。或者等效地，长度为 n+2 且以 d1、d2 开头的有效序列数。K[n, d1, d2]

存在满足以下条件的递归关系：K

K[n, d1, d2] = 0 if d1=d2 or d1 is not coprime to d2.
K[0, d1, d2] = 1
K[n, d1, d2] = sum(K[n-1, d2, d] for d=1..6 - {d1, d2})

这可以使用自下而上的动态程序或记忆来计算。K

原来的问题可以解决，这样可以：n>=2

S[n] = sum(K[n-2, d1, d2] for d1=1..6, d2=1..6)

对于 ，我们有 和 。n<=2S[0] = 1S[1] = 6

使用 O（1） 空间和 O（n） 时间编写此代码的一种方法是：

from math import gcd

def S(n):
    if n == 0: return 1
    if n == 1: return 6
    K = [d1!=d2 and gcd(d1+1, d2+1)==1 for d1 in range(6) for d2 in range(6)]
    for _ in range(n-2):
        K = [0 if d1==d2 or gcd(d1+1, d2+1)!=1 else sum(K[d2*6+d] for d in range(6) if d!= d1 and d!=d2) for d1 in range(6) for d2 in range(6)]
    return sum(K)

这将从 开始迭代计算。K[n,_,_]K[n-1,_,_]

接下来可以出现的数字仅取决于前两个数字。所以这里有一个迭代解决方案，它只保留 O（1） 个数字，它的速度大约是 N=2000 时 Tomer 的两倍（即使没有任何优化，我什至一直在调用）：gcd

from collections import Counter
from math import gcd

def count_seq(N):
    ctr = Counter([(7, 7)])
    for _ in range(N):
        temp = Counter()
        for (a, b), count in ctr.items():
            for c in range(1, 7):
                if c != a and c != b and gcd(b, c) == 1:
                    temp[b, c] += count
        ctr = temp
    return sum(ctr.values())

My 是一个哈希映射，其键是代表最后两个数字的对，这些值告诉有多少个有效序列以这两个数字结尾。初始化为，因为这允许所有扩展。ctr(7, 7)

为了获得乐趣和最大性能，对所有状态和转换进行硬编码，这比我上面的 N=2000 解决方案快约 14 倍，并在大约 10 秒内解决 N=100,000（结果是一个具有 45,077 位数字的数字）：

def count_seq(N):
    if N < 2:
        return 6 if N else 1
    x12 = x13 = x14 = x15 = x16 = x21 = x23 = x25 = x31 = x32 = x34 = x35 = x41 = x43 = x45 = x51 = x52 = x53 = x54 = x56 = x61 = x65 = 1
    for _ in range(N - 2):
        x12, x13, x14, x15, x16, x21, x23, x25, x31, x32, x34, x35, x41, x43, x45, x51, x52, x53, x54, x56, x61, x65, = x31+x41+x51+x61, x21+x41+x51+x61, x21+x31+x51+x61, x21+x31+x41+x61, x21+x31+x41+x51, x32+x52, x12+x52, x12+x32, x23+x43+x53, x13+x43+x53, x13+x23+x53, x13+x23+x43, x34+x54, x14+x54, x14+x34, x25+x35+x45+x65, x15+x35+x45+x65, x15+x25+x45+x65, x15+x25+x35+x65, x15+x25+x35+x45, x56, x16
    return x12 + x13 + x14 + x15 + x16 + x21 + x23 + x25 + x31 + x32 + x34 + x35 + x41 + x43 + x45 + x51 + x52 + x53 + x54 + x56 + x61 + x65

例如，这里是以数字 2 和 3 结尾的有效序列的数量。还有进一步微优化的空间（使用额外的变量在 和 之间交替，而不是构建+解包元组，或利用像 这样的常见子和，它被使用了三次），但我会把它留在这里。x23yxyx21+x41

哦，其实......正如斐波那契数列所看到的那样，我们可以将跃迁表示为 22×22 矩阵，然后通过平方快速计算该矩阵的 N 次（或 N-2）次幂。这应该更快。

呃......现在实现了矩阵幂方法，可惜它的速度较慢。我想它真的只有在你只需要某种截断值时才有帮助，比如只有第一个或最后一个 100 位数字和位数，或者序列数取模某个数字。否则，虽然矩阵幂方法确实需要较少的运算，但它们包括大数的乘法，而不仅仅是加法，这速度较慢。无论如何，这是我的实现（在线尝试！

from math import gcd
import numpy as np

def count_seq(N):
    if N < 2:
        return 6 if N else 1
    states = [(a, b) for a in range(1, 7) for b in range(1, 7) if a != b and gcd(a, b) == 1]
    A = [[1 if b2 == b and a != c else 0
          for b2, c in states]
         for a, b in states]
    return (np.matrix(A, dtype=object) ** (N-2)).sum()

作为演示，下面是一个计算最后三位数字的修改。对于 N=100,000，大约需要 0.26 秒，对于 N=1,000,000,000,000,000,000,000，大约需要一秒钟。

def count_seq(N):
    if N < 2:
        return 6 if N else 1
    modulo = 1000
    class IntModulo:
        def __init__(self, value):
            self.value = value
        def __add__(self, other):
            return IntModulo((self.value + other.value) % modulo)
        def __mul__(self, other):
            return IntModulo((self.value * other.value) % modulo)
        def __int__(self):
            return self.value
    states = [(a, b) for a in range(1, 7) for b in range(1, 7) if a != b and gcd(a, b) == 1]
    A = [[IntModulo(1 if b2 == b and a != c else 0)
          for b2, c in states]
         for a, b in states]
    return int((np.matrix(A, dtype=object) ** (N-2)).sum())