algorithm - 从保存的状态恢复递归函数

Question

我有一个递归函数，它从一组 n 中产生长度为 k 的所有组合。通常称为“nCk”(“n 选择 k”)。我希望将其设置为相当大的值 (56C22)，这将产生 2,142,582,442,263,900 个结果。由于实现的限制(我必须使用VBScript，并且不能比我在工作时保持登录计算机的时间更长)，我无法让它一次性运行完成。因此，我想定期保存函数的当前状态并在以后恢复它……但我似乎不知道该怎么做。递归干扰了我从逻辑上思考这个问题的能力。

我已经仔细阅读了此处关于 SO 的建议解决方案，并以其他方式搜索了“恢复递归函数”等，但无济于事。我会很感激一些指示(不是编程语言双关语)让我走上正确的轨道。

实际的算法(伪代码也可以)优于不包含实际代码的冗长解释。如果您想实际编写代码，我最熟悉 C、C++、Pascal、VB、JavaScript 和 VBScript(并且，如前所述，目前正在使用 VBScript)。

这是我的递归函数:

function nCk(aSet, iSetIndex, aSubset, iSubsetIndex)
    'Found result
    if (iSubsetIndex > ubound(aSubset)) then
        log "output.txt", join(aSubset), 1, false

        exit function
    end if

    'No more characters available
    if (iSetIndex >= ubound(aSet) + 1) then
        exit function
    end if

    'With aSet[iSetIndex]
    aSubset(iSubsetIndex) = aSet(iSetIndex)
    nCk aSet, iSetIndex + 1, aSubset, iSubsetIndex + 1

    'Without
    nCk aSet, iSetIndex + 1, aSubset, iSubsetIndex
end function  'nCk

仅供引用:我今年 50 岁；这不是家庭作业。

Answer 1

存储递归并不是那么容易，因为要恢复操作，您需要恢复堆栈，这不是一项简单的任务。我会使用迭代算法，它不如递归优雅。但如果需要中断/恢复计算，它会带来返回。

一个想法可以是:

1. 子集表示为 0 和 1 的向量。 0 表示元素未被采用，1 - 元素被采用，因此集合 {1,2,3} 的 [1, 0, 1] 表示子集 {1,3}。显然只有长度为 N 的向量是实子集。
2. 将此向量视为一种堆栈，它代表您“递归”的状态
3. 此向量中的值 -1 用于触发迭代中的正确行为 -> 类似于从递归返回/回溯。

作为算法(首先，迭代所有子集):

def calc_subsets(state, N):#N - number of elements in the original set
     while True: #just iterate
        if storeFlag:#you need to set this flag to store and interrupt
            store(state)
            return
        if len(state)==N and state[-1]!=-1: #a full subset is reached
            evaluate(state)
            state.append(-1)#mark for unwind

        if state[-1]==-1:#means unwind state
            state.pop()
            if not state: #state is empty
                return #unwinded last element, we are done
            if state[-1]==1:#there is noting more to be explored
               state[-1]=-1#mark for unwind in the next iteration
            else:# = 0 is explored, so 1 is the next to explore
               state[-1]=1
        else: #means explore
            state.append(0) # 0 is the first to explore

evaluate 由你决定，我只是打印出向量:

def evaluate(state):
    print state

要打印 3 个元素的所有子集，应该调用:

calc_subsets([0], 3)
>>>
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

并且只打印第二部分:

calc_subsets([0,1,1,-1], 3) 
>>>
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

现在，该算法可以调整为仅迭代具有给定基数的所有子集。为此，必须跟踪当前子集中的元素数量，并在达到请求的子集大小时触发展开(通过将 -1 插入状态向量)。