So I am working on an iterative backtracking algorithm to solve this task:

Generate all subsequences of length 2n 1, formed only by 0, -1 or 1, such that a₁ = 0, ..., a_{2n 1}= 0 and |a_{i 1} - a_i| = 1 or 2, for any 1 ≤ i ≤ 2n.

This is what I tried:

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

My output for n=2:

[0, -1, 0, -1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, -1, 0]
[0, 1, 0, -1, 0]

Expected output for 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]

CodePudding user response：

everything is correct in your code, but you are printing at wrong place

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]