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

为了解决这个问题，我们将遵循以下步骤−

定义backtrack()函数。这将需要elems，res，start := 0
如果elems的大小≤0，则
- 返回True
如果start≥res的大小，则
- 返回False
如果res [start]与-1不同，则
- 返回backtrack(elems，res，start + 1)
对于范围在0到elems大小-1之间的i，进行以下操作
- num：= elems [i]
- 当num等于1时，dist：= 0，否则为num
- 如果(start + dist)
  - res [start]：= num
  - res [start + dist]：= num
  - 从elems中删除第i个元素
  - 如果backtrack(elems，res，start)为false，则
  - res [start]：= -1
  - res [start + dist]：= -1
  - 在第i个位置将num插入elems中
  - 进入下一次迭代
  - 否则，
  - 返回True
从main方法中执行以下操作
elems：=具有从n到1的n个元素的列表
res：=大小为n*2-1的list，并用-1填充
backtrack(elems，res)
返回res

例

让我们看一下以下实现，以获得更好的理解−

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