non-decreasing sub-sequence backtracking.py

"""
Given a binary sequence X of length n, write an algorithm that prints all
non-decreasing sub-sequences that contain at least one 1 and 0.
"""

def backtracking(X):

    def back(X, S, i, last_item, last_one):

        # reached max length
        if i == len(X):
            print(' '.join(str(n) for n in S))
            return S
        
        
        if last_item == 0 and i > last_one:
            return

        # element is part of non-decreasing sequence
        if last_item == None or X[i] >= last_item:
            
            S[i] = X[i]

            # if we find a 0 we can add it
            if X[i] == 0:
                back(X, S, i + 1, X[i], last_one)
            
            # if we find a 1 and we've already begun the subsequence, add it
            elif not last_item is None:
                back(X, S, i + 1, X[i], last_one)

        # don't add underscore if this is last 1 in sequence and only had 0's before
        if i == last_one and (last_item == 0 or last_item is None):
            return

        # give solutions with underscore as well
        S[i] = "_"
        back(X, S, i + 1, last_item, last_one)
        return 
    

    #### analyse the string ####

    last_one = first_zero = None

    # loop backwards to find last 1 and first 0
    for d in range(len(X)-1, -1, -1):

        # this stops entering once last_one is found
        if X[d] == 1 and last_one is None:
            last_one = d
        
        # this only begins entering once last_one is found
        # continues updating first_zero until done looping
        if X[d] == 0 and not last_one is None:
            first_zero = d
    
    # if no 0's or 1's found, or first 0 is after last 1, return
    if last_one is None or first_zero is None:
        return None

    return back(X, [None] * len(X), 0, None, last_one)
    


backtracking([0, 1, 0, 1])
assert backtracking([1, 1, 1, 1]) is None
assert backtracking([1, 1, 1, 0]) is None
assert backtracking([1, 1, 0, 0]) is None
assert backtracking([1, 0, 0, 0]) is None
assert backtracking([0, 0, 0, 0]) is None


"""
Result:
0 1 _ 1
0 1 _ _
0 _ 0 1
0 _ _ 1
_ _ 0 1
"""