保存された状態からの再帰関数の再開

Question

私は、nのセットから長さkのすべての組み合わせを生成する再帰関数を持っています。典型的には「nCk」（「nはkを選択する」）と呼ばれる。私はかなり大きな値（56C22）でそれを緩くして、2,142,582,442,263,900の結果を生み出すことを望みます。実装上の制約（私はVBScriptを使用しなければならず、私が仕事中よりも長い間コンピュータにログインしたままにすることができません）では、完了まで一度に実行することはできません。そのように、私は定期的に関数の現在の状態を保存し、後で再開したいと思います...しかし、私はそうする方法を見つけることができないようです。再帰は、論理的にこれを考える能力を乱している。

私はここで提案された解決策を熟読しており、そうでなければ "再帰的機能の再開"などを無駄に検索しています。私は適切なトラックに私を得るためにいくつかのポインタ（プログラミング言語ではない）を感謝します。

実際のアルゴリズムを含む実際のアルゴリズム（擬似コードは問題ありません）は、実際のコードを含まない長時間の説明よりも優先されます。実際にコードを作成したいのであれば、C、C++、Pascal、VB、JavaScript、VBScriptに精通しています（現時点でVBScriptを使って作業しています）。ここで

は私の再帰関数である：FYI

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,3}を意味する[1,0,1]となる。明らかに、長さ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] 

次に、アルゴリズムのみ与えられた基数を持つすべてのサブセットを反復処理するように構成することができる：10とは、第二の部分を印刷します。そのためには、現在のサブセットの要素数を追跡し、要求されたサブセットのサイズが達成された場合に、アンワインディング（状態ベクトルに-1をプッシュすることによって）をトリガする必要があります。

Answer 2

具体的な言語の実装についてはわかりませんが、特定の状況では反復を反復に変換するのがよいと思います。明示的なスタックを持っているときは、それをディスクに書き込んだり、途中で中断した部分を取り上げたりするのはあまり複雑ではありません。

一般的な例：あなたは簡単な作業ではありませんスタックを、復元する必要があります動作を再開するための再帰を保存

stack = [[argument1,argument2,argument3,...etc.]] 

while stack is not empty 
    current_parameters = stack.pop 

    aSet  = current_parameters[0] 
    iSetIndex = current_parameters[1] 
    ...etc. 

    if ... 

else ... 
    // push to stack instead of calling nCk 
    stack.push([aSet, iSetIndex + 1, aSubset, iSubsetIndex + 1]) 

if it's time to go home 
    write stack to disc 
    break