从左往右每个格子依次放每个数 (注意到放了一个数以后第二次出现一定在右边 且位置确定)。 放不下去了就回溯。
状态空间就是放满的前缀
def twice_distance(n):
init = [0 for i in range(2*n)]
return find_all(n, init, 0, set())
def find_all(n, arr, next_pos, selected):
while next_pos < len(arr) and arr[next_pos] != 0:
next_pos += 1
if next_pos == len(arr):
return [arr.copy()]
ans = []
for i in range(1, n+1):
other_pos = next_pos + i + 1
if not i in selected and other_pos < len(arr) and arr[other_pos] == 0:
arr[next_pos] = i
arr[other_pos] = i
selected.add(i)
ans += find_all(n, arr, next_pos+1, selected)
selected.remove(i)
arr[next_pos] = 0
arr[other_pos] = 0
return ans
print(twice_distance(4))
# [[2, 3, 4, 2, 1, 3, 1, 4], [4, 1, 3, 1, 2, 4, 3, 2]]
如果太慢再考虑优化一下