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

Question

问题是在给定的约束下找到有效序列 (A1,A2...AN) 的数量：

1. Ai 的值介于 1 和 6 之间（1<= Ai <= 6）
2. 两个相邻的数字应该是互质的。对于例如 2,4,.. 序列是不允许的
3. 如果该值在序列中重复，则它们的索引差异应大于 2。对于例如如果 K=4，(1,2,3,1) 是有效的序列 while (1,3,4,3) 不是有效序列
   注：N 在问题陈述中给出。

我只能想到一个回溯解决方案，其中每个递归调用都会针对给定的 Ai 位置尝试从 1 到 6 的所有数字。
这看起来更像是暴力方式。 请您帮忙提供一个最佳解决方案。

Answer 1

我们可以使用这样一个事实，即只能使用6个可能的数字来构建数字。

1. 考虑一个查找表 dp [i] [j] [k] ，它基本上是 i-digit数字的计数，i-th Digit作为j，（i-1）数字作为k 。
2. 为每个数字创建所有有效的共同准则的映射。类似 {2：[1,3,5]，3：[1,2,4,5]，6：[1,5]} ...
3. 基本案例： dp [0] = 0对于所有j，k ， dp [1] = 0对于所有J，k ， dp [2] [j] [j] [k] = 1，如果1 gcd（j，k）== 1和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))

Answer 2

令 K[n, d1, d2] 为长度为 n 的有效序列的数量，这样如果 d1、d2 恰好出现在前面，则该序列仍然有效。或者等效地，以 d1、d2 开头的长度为 n+2 的有效序列的数量。

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<=2，我们有 S[0] = 1和S[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-1, _,_]。

Answer 3

这里有一个图形搜索问题，可以使用回溯搜索来解决，并且可以使用 记忆。

定义状态

遵循问题中的规则，状态是元组，其中元组中的第一个值是当前数字 a_n 和系列中的前一个数字 a_{n-1}< /code> 元组中的第二个值是序列的长度，因为数字的出现可以在 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)，所需序列长度为 5。在这种情况下，后面的数字不能是 2,3（以保持距离至少 2) 或 6 (以保持相邻数字互质），因此总共有以下状态：

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

说明

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

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

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)

Answer 4

接下来可以出现什么数字仅取决于前两个数字。因此，这里有一个迭代解决方案，仅保留 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 < code>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

这里，例如x23 是以数字 2 和 3 结尾的有效序列的数量。还有进一步微优化的空间（使用额外的y 变量在 x 和 y 之间交替，而不是构建+解包元组，或利用常见的子和，例如 x21+x41 >，使用了三次），但我就到此为止吧。

哦，实际上...正如人们在斐波那契数中看到的那样，我们可以将转换表示为 22×22 矩阵，然后通过平方求幂快速计算该矩阵的 N 次（或 N-2 次）幂。那应该更快。

嗯...现在实现了矩阵幂方法，遗憾的是它慢。我想它只有在您只需要某种截断值（例如仅前 100 位或后 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，大约需要 1 秒。

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())