在 Python 中构建字典序最大有效序列的程序
假设我们有一个数字 n，我们必须找到一个满足以下所有规则的序列 -
1 在序列中出现一次。
2 和 n 之间的每个数字在序列中出现两次。
对于 2 到 n 范围内的每个 i，i 的两次出现之间的距离正好是 i。
序列上的两个数字 a[i] 和 a[j] 之间的距离是 |j - i|。我们必须找到字典序最大的序列。
所以，如果输入像 n = 4，那么输出将是 [4, 2, 3, 2, 4, 3, 1]
示例
让我们看看以下实现以获得更好的理解 -
def backtrack(elems, res, start = 0):if len(elems) <= 0:
return True
if start >= len(res):
return False
if res[start] != -1:
return backtrack(elems, res, start + 1)
for i in range(len(elems)):
num = elems[i]
dist = 0 if num == 1 else num
if (start + dist) < len(res) and res[start + dist] == -1:
res[start] = num
res[start + dist] = num
elems.pop(i)
if not backtrack(elems, res, start):
res[start] = -1
res[start + dist] = -1
elems.insert(i, num)
continue
else:
return True
def solve(n):
elems = [ i for i in range(n,0,-1)]
res = [ -1 for i in range(n*2 - 1)]
backtrack(elems, res)
return res
n = 4
print(solve(n))
输入
4输出结果
[4, 2, 3, 2, 4, 3, 1]
以上是 在 Python 中构建字典序最大有效序列的程序 的全部内容， 来源链接： utcz.com/z/360946.html
