在 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]