q4.py

def backtrack(R, D, used_numbers):
    if R:
        used_numbers[R[-1]] = False
        R.pop()
    if D:
        D.pop()
    
def ordering(k):
    def ordered_R(R):
        if len(R) == k:
            return R
        else:
            for num in range(k):
                if used_numbers[num]:
                    continue
                if R:
                    diff = (num - R[-1]) % k
                    if D and diff < D[-1]:
                        continue
                    else:
                        D.append(diff)
                R.append(num)
                used_numbers[num] = True
                result = ordered_R(R)
                if result:
                    return result
            backtrack(R, D, used_numbers)
        return None
    D = []
    R = []
    used_numbers = [False] * k
    return ordered_R(R)

def all_orderings(k):
    def find_all_orderings(R):
        if len(R) == k:
            final_orderings.append(R[:])
        else:
            for num in range(k):
                if used_numbers[num]:
                    continue
                if R:
                    diff = (num - R[-1]) % k
                    if D and diff < D[-1]:
                        continue
                    else:
                        D.append(diff)
                R.append(num)
                used_numbers[num] = True
                find_all_orderings(R)
        backtrack(R, D, used_numbers)
    D = []
    R = []
    used_numbers = [False] * k
    final_orderings = []
    find_all_orderings(R)
    return final_orderings