Pythonで辞書式順序で最大の有効なシーケンスを構築するプログラム

数nがあるとすると、次のすべてのルールを満たすシーケンスを見つける必要があります-

• 1はシーケンスで1回発生します。

• 2からnまでの各数字は、シーケンス内で2回出現します。

• 2からnの範囲のすべてのiについて、iの2つの出現間の距離は正確にiです。

シーケンス上の2つの数値a[i]とa[j]の間の距離は、| j--i|です。字句的に最大のシーケンスを見つける必要があります。

したがって、入力がn =4の場合、出力は[4、2、3、2、4、3、1]

これを解決するには、次の手順に従います-

• 関数backtrack（）を定義します。これには、elems、res、start：=0
が必要です。
• 要素のサイズが<=0の場合、
  • Trueを返す
• start> =resのサイズの場合、
  • Falseを返す
• res [start]が-1と同じでない場合、
  • return backtrack（elems、res、start + 1）
• 0から要素のサイズ-1までの範囲のiの場合、実行します
  • num：=elems [i]
  • numが1と同じ場合はdist：=0、それ以外の場合はnum
  • if（start + dist）
  • res [start]：=num
  • res [start + dist]：=num
  • 要素からi番目の要素を削除する
  • backtrack（elems、res、start）がfalseの場合、
    • res [start]：=-1
    • res [start + dist]：=-1
    • 位置iの要素にnumを挿入します
    • 次の反復に進む
  • それ以外の場合、
    • Trueを返す

例

理解を深めるために、次の実装を見てみましょう-

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]