满足给定约束的有效序列数
Number of valid sequences that satisfies given constraints
问题是找到具有给定约束的有效序列 (A1,A2....AN) 的数量：
- Ai 的值介于 1 和 6 之间（1<= Ai <= 6）
- 相邻的两个数应该互质。例如2,4,.. 序列不允许
- 如果值在序列中重复，那么它们的索引差应该大于2。例如如果 K=4，则 (1,2,3,1) 是有效序列，而 (1,3,4,3) 不是有效序列
注：N在问题陈述中给出。
我只能想到一个回溯解决方案，其中每个递归调用都会为给定的 Ai 位置尝试从 1 到 6 的所有数字。
这看起来更像是蛮力方式。
能否请您帮忙出一个最优解。
你这里有一个图形搜索问题，可以使用回溯搜索来解决，并且可以使用 memoization.
更快地 运行
定义状态
按照问题中的规则，状态是元组，其中元组中的第一个值是当前数字 a_n 和系列中的前一个数字 a_{n-1} 以及系列中的第二个值元组是序列的长度，因为数字的出现可以在 2 或更多的间隔内。
此外，禁止状态是两个数字不是co-prime的状态，这意味着
的每个排列
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（保持相邻的数字 co-prime）所以总共有以下状态：
- ((3,1), 4)
- ((3,4), 4)
- ((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，因为任何一个数字都可以位于第一个位置。
我们看看开始状态是否是None我们假设这是初始调用，所以我们创建所有可能的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 个可能的数字来构造数字这一事实。
- 考虑查找 table
dp[i][j][k]，它基本上是 count of i-digit numbers with the i-th digit as j, (i-1)th digit as k.
- 为每个数字创建所有有效 co-primes 的映射。像
{2: [1,3,5], 3: [1,2,4,5], 6: [1,5]}...
- 基本案例：
dp[0] = 0 for all j,k、dp[1] = 0 for all j,k、dp[2][j][k] = 1 if gcd(j,k)==1 and j!=k
- 现在填写 table 应该比较简单了。
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
- 最终答案=
sum(dp[N][1..6])
它的时间和 space 复杂度为 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))
令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 可以使用 bottom-up 动态程序或记忆来计算。
原来的问题可以解决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) space 和 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,_,_] 迭代计算 K[n,_,_]。
下一个数是多少只取决于前两个数。所以这是一个只保留 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())
我的 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 位数字和位数，或者序列数对某个数字取模。否则，虽然矩阵幂方法确实需要更少的运算，但它们包括大数的 乘法 而不是仅 加法 ，后者速度较慢。无论如何，这是我的实现 (Try it online!):
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())
问题是找到具有给定约束的有效序列 (A1,A2....AN) 的数量：
- Ai 的值介于 1 和 6 之间（1<= Ai <= 6）
- 相邻的两个数应该互质。例如2,4,.. 序列不允许
- 如果值在序列中重复，那么它们的索引差应该大于2。例如如果 K=4，则 (1,2,3,1) 是有效序列，而 (1,3,4,3) 不是有效序列
注：N在问题陈述中给出。
我只能想到一个回溯解决方案，其中每个递归调用都会为给定的 Ai 位置尝试从 1 到 6 的所有数字。
这看起来更像是蛮力方式。
能否请您帮忙出一个最优解。
你这里有一个图形搜索问题，可以使用回溯搜索来解决，并且可以使用 memoization.
更快地 运行定义状态
按照问题中的规则，状态是元组，其中元组中的第一个值是当前数字 a_n 和系列中的前一个数字 a_{n-1} 以及系列中的第二个值元组是序列的长度，因为数字的出现可以在 2 或更多的间隔内。
此外，禁止状态是两个数字不是co-prime的状态，这意味着
的每个排列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（保持相邻的数字 co-prime）所以总共有以下状态：
- ((3,1), 4)
- ((3,4), 4)
- ((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，因为任何一个数字都可以位于第一个位置。
我们看看开始状态是否是
None我们假设这是初始调用，所以我们创建所有可能的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 个可能的数字来构造数字这一事实。
- 考虑查找 table
dp[i][j][k]，它基本上是count of i-digit numbers with the i-th digit as j, (i-1)th digit as k. - 为每个数字创建所有有效 co-primes 的映射。像
{2: [1,3,5], 3: [1,2,4,5], 6: [1,5]}... - 基本案例：
dp[0] = 0 for all j,k、dp[1] = 0 for all j,k、dp[2][j][k] = 1 if gcd(j,k)==1 and j!=k - 现在填写 table 应该比较简单了。
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
- 最终答案=
sum(dp[N][1..6])
它的时间和 space 复杂度为 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))
令K[n, d1, d2]为长度为n的有效序列的数量，使得如果d1、d2恰好出现在前面，该序列仍然有效。或者等价地，以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 可以使用 bottom-up 动态程序或记忆来计算。
原来的问题可以解决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) space 和 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,_,_] 迭代计算 K[n,_,_]。
下一个数是多少只取决于前两个数。所以这是一个只保留 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())
我的 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 位数字和位数，或者序列数对某个数字取模。否则，虽然矩阵幂方法确实需要更少的运算，但它们包括大数的 乘法 而不是仅 加法 ，后者速度较慢。无论如何，这是我的实现 (Try it online!):
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())