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() 함수를 정의합니다. 이것은 요소, 해상도, 시작이 필요합니다 :=0
• 요소의 크기가 <=0이면
  • 참 반환
• 시작>=res의 크기이면
  • 거짓을 반환
• res[start]가 -1과 같지 않으면
  • 되돌리기(요소, 해상도, 시작 + 1)
• 요소의 크기가 0에서 1인 범위에 있는 i에 대해
  • num :=요소[i]
  • dist :=num이 1이면 0, 아니면 num
  • if (start + dist)
  • res[시작] :=숫자
  • res[시작 + 거리] :=숫자
  • 요소에서 i번째 요소 삭제
  • 백트랙(elems, res, start)이 거짓이면
    • res[시작] :=-1
    • res[시작 + 거리] :=-1
    • 위치 i의 요소에 num 삽입
    • 다음 반복으로 이동
  • 그렇지 않으면
    • 참 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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]