在回溯中记住列表

Question

我正在解决一个问题，要求我生成一个包含所有差异值的数组。回溯自然似乎是这里使用的方法，但我对回溯的基本原理有一些问题。 每个节点都有一个 choiceList，我必须从中选择一个元素并测试条件。

但是假设条件失败（在某个叶节点）并且我回溯，我如何记住那个阶段的

choiceList

？

我的代码：

def arrayGen(n,N,proto,choiceList,i):
    proto[-1] = N

    if None not in proto:
        lst = diffChecker(proto)
        if 0 in lst or 1 in lst: #now we backtrack
            print(f"{proto} is not a solution\n")
            return
        else:
            print(f"{proto} is a solution\n")

            return

    if not choiceList: #choicelist is empty
        print(f"{proto} contains None\n")
        return


    if proto[i] is None:
        proto[i] = choiceList[0]
        choiceList.pop(0)
        arrayGen(n,N,proto,choiceList,i+1)
        proto[i] = None
        arrayGen(n,N,proto,choiceList,i)
    else:
        arrayGen(n,N,proto,choiceList,i+1)

[子空间照片（如果有帮助的话）][1]

[1]: 盒装列表是选择列表。

我遇到的主要问题是在 [0,1,2,5,6] 节点回溯后，ChoiceList 变空。我希望它恢复到原来的样子。因此，当我从 [0,1,2,5,6] 回溯到 [0,1,2,None,6] 时，它应该检测到，由于 choiceList 为空，所以这里所有可能的组合都已被探索过，并且应该返回再次跟踪到 [0,1,None,None,6]，这里的 choiceList 应恢复到 {2,3,4,5} - {2} = {3,4,5}，因为 {2} 已被使用到现在为止。

我意识到我没有说清楚，我很抱歉。我需要的是关于如何在此类问题中执行回溯的见解？

编辑- diffChecker 函数（检查相关条件是否成功/失败）

def diffChecker(lst):
    result = [0]*(lst[-1]+1)
    dontCount = set()
    result[0] = 2
    result[-1] = 2
    for i in range(1,lst[-1]):#diff_Values
        dontCount = set()
        for j in lst:
            if j == None:
                continue
            if((j + i) in lst and frozenset((j,j+i)) not in dontCount):
                result[i] += 1
                dontCount.add(frozenset((j,j+i)))
            elif((j-i) in lst and frozenset((j,j-i)) not in dontCount):
                result[i] += 1
                dontCount.add(frozenset((j,j-i)))
    return result

驱动程序代码-

#driver/main code-
n = int(input("Enter array size: "))
N = n+1 # dynamic upper limit
proto = [None]*n #length of resultant array is fixed
proto[0] = 0 #first element is always 0
proto[-1] = N
diff_table = [0]*(N+1)
diff_table[-1] = 2 #in actuality it is 1, but for efficiency purposes we've put = 2
diff_table[0] = 2
current_diff = 1 # since diff val of 0 is already present twice - (0-0) & (N-N)
choiceList = []
for i in range(1,N):
    choiceList.append(i)
i = 0
arrayGen(n,N,proto,choiceList,i)

输入/输出场景示例（当前）-

Enter array size: 5
#now, we try to generate all array combinations that satisfy the diffChecker function from this via backtracking

[0, 1, 2, 3, 6] is not a solution

[0, 1, 2, 4, 6] is not a solution


[0, 1, 2, 4, 6] is not a solution

[0, 1, 2, 5, 6] is not a solution


[0, 1, 2, None, 6] contains None

[0, 1, None, None, 6] contains None
#from this part on, the code should not backtrack again. Refer to the attached picture on how exactly I'm trying to fill up the None spots

#expected- [0,1,3,None,None,6] ->(advance) [0,1,3,4,None,6] ->....

[0, None, None, None, 6] contains None

Answer 1

基本上有两种记住先前状态以进行回溯的策略：

1. 请勿修改状态。相反，将状态的完整“新”副本传递到下一个级别。当状态较小且简单时，您就会这样做。

在将状态传递到下一级之前修改状态，但要记住
2. undo

   信息并在回溯时撤消修改。当状态太大或太复杂而无法每次都制作新副本时，您就会这样做。

您可以针对该州的不同地区混合搭配这些方法。如果看起来您应该使用撤消策略来进行数组修改：

    if proto[i] is None:

        # modify state and remember undo information
        protoUndo = proto[i]
        proto[i] = choiceList[0]
        choiceListUndo = choiceList.pop(0)

        # pass state to next level
        arrayGen(n,N,proto,choiceList,i+1)
        proto[i] = None
        arrayGen(n,N,proto,choiceList,i)

        # undo modifications
        proto[i] = protoUndo
        choiceList.insert(0, choiceListUndo)
    else:
        arrayGen(n,N,proto,choiceList,i+1)