9.3

Key observation: the required arrangement is a Langford pairing L(2,n). Such a pairing exists iff n = 0 or n ≡ 0,3 (mod 4). For every other n the answer set is empty.

Back-tracking generator Keep an array A[2n] filled with 0. Place numbers from n down to 1; to place k choose an index i with A[i]=A[i+k+1]=0, then set A[i]=A[i+k+1]=k and recurse on k−1. When k becomes 0 the array is a full permutation, so append it to the answer list. To avoid mirror duplicates fix the first occurrence of n to lie in the left half of the array.

Pseudocode solve(n):
  if n % 4 not in (0,3): return [] # existence test
  A = [0]*(2*n); ans=[]
  def place(k):
    if k==0: ans.append(A.copy()); return
    for i in range(2*n-k-1): # j = i+k+1 inside array
      j=i+k+1
      if A[i]==A[j]==0:
        A[i]=A[j]=k
        place(k-1)
        A[i]=A[j]=0 # back-track
  place(n)
  return ans

Compact Python implementation

def langford(n):   if n % 4 not in (0,3):     return []   slots=[0]*(2*n); res=[]   def dfs(k):     if k==0:       res.append(slots.copy())       return     for i in range(2*n-k-1):       j=i+k+1       if slots[i]==slots[j]==0:         slots[i]=slots[j]=k         dfs(k-1)         slots[i]=slots[j]=0   dfs(n)   return res

Example (n = 3): langford(3) returns [3, 1, 2, 1, 3, 2] and [2, 3, 1, 2, 1, 3].

Complexities: worst-case search O((2n)!/2ⁿ) but heavily pruned; memory O(n).

Hence all required permutations are exactly the Langford pairings generated by the above routine, and they exist only when n ≡ 0 or 3 mod 4.

Back to Chapter 9