所以我正在研究一個迭代回溯演算法來解決這個任務：
生成所有長度為 2n 1 的子序列，僅由 0、-1 或 1 組成，使得 a 1 = 0, ..., a 2n 1 = 0 和 |a i 1 - a i | = 1 或 2，對于任何 1 ≤ i ≤ 2n。
這是我嘗試過的：
def is_ok(list, k):
for i in range(1, k 1):
if abs(list[i] - list[i-1]) == 0:
return False
if k == len(list)-2:
if abs(list[k 1]-list[k]) == 0:
return False
return True
def back_iter(n):
list_size = n*2 1
solution = [-1] * list_size
solution[0] = 0
solution[2*n] = 0
position = 1
while position >= 1:
if is_ok(solution, position) and position < 2*n-1:
if position == 2*n-2:
print(solution)
position = 1
solution[position] = -1
else:
while solution[position] == 1:
solution[position] = -1
position -= 1
if position < 1:
break
solution[position] = 1
我的 n=2 輸出：
[0, -1, 0, -1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, -1, 0]
[0, 1, 0, -1, 0]
n=2 的預期輸出：
[0, -1, 0, -1, 0]
[0, -1, 0, 1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, 1, 0]
[0, 1, 0, -1, 0]
[0, 1, 0, 1, 0]
uj5u.com熱心網友回復：
您的代碼中的一切都是正確的，但是您在錯誤的位置列印
def is_ok(arr, i):
return abs(arr[i]-arr[i-1]) in (1,2)
def back_iter(n):
list_size = n*2 1
solution = [-1] * list_size
solution[0] = 0
solution[2*n] = 0
position = 1
while position >= 1:
if is_ok(solution, position) and position < 2*n-1:
position = 1
solution[position] = -1
else:
if is_ok(solution, position) and position == (2*n-1) and solution[position]:
print(solution)
while solution[position] == 1:
solution[position] = -1
position -= 1
if position < 1:
break
solution[position] = 1
back_iter(2)
# output
[0, -1, 0, -1, 0]
[0, -1, 0, 1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, 1, 0]
[0, 1, 0, -1, 0]
[0, 1, 0, 1, 0]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/527270.html