將遞歸置換生成器轉換爲迭代

Question

我在將此遞歸算法轉換爲將給定的整數集合的所有排列顯示爲迭代算法時遇到了一些困難。

void getPermutationsR(int v[], int n, int i) 
{ 
    if (i == n) 
    { 
     //Display contents of v 
    } 
    else 
    { 
     for (int j=i; j<n; j++) 
     { 
      swap (v, i, j); 
      getPermutationsR(v, n, i+1); 
      swap (v, i, j); 
     } 
    } 
} 

這是我當前的嘗試，它是完全錯誤的，但我看不出有什麼辦法來糾正它不使用本地迭代算法問題。我的一半嘗試讓我'彈出'超過'推'（導致錯誤，因爲我試圖訪問空堆棧中的元素），另一半我'推'超過'爆裂'（無限循環）。

void getPermutationsI(int v[], int n, int i) 
    { 
    stack<int> iStack; 
    stack<int> jStack; 

    iStack.push(i); 
    jStack.push(i); 

    while(iStack.size() > 0) 
    { 
     if (iStack.top() == n) 
     { 
      jStack.pop(); 
      iStack.pop(); 
      //Display contents of v 
     } 
     else 
     { 
      for (int j = iStack.top(); j < n; j++) 
      { 
       //swap 
           //something to do with jStack 
      } 
      //swap 
      iStack.push(i+1); 
     } 
    } 
} 

Answer 1

您遇到的挑戰是您的函數調用和循環結構混雜在一起。這很難解開這些。

首先讓我們開始用遞歸替換流操作的所有控制。

// You'll want to start with getPermutionsR(v, n, 0, 0) 
void getPermutationsR(int v[], int n, int i, int j) 
{ 
    if (i == n) 
    { 
     //Display contents of v 
    } 
    else if (j == n) { 
     // By doing nothing, we break out of the loop 
    } 
    else 
    { 
     // This was your recursive call inside of the loop. 
     // Note that I'm sending you to to the first loop iteration here. 
     swap (v, i, j); 
     getPermutationsR(v, n, i+1, i+1); 
     swap (v, i, j); 

     // And the next loop iteration 
     getPermutationsR(v, n, i, j+1); 
    } 
} 

接下來讓我們添加更多的狀態，這樣我們只有一個遞歸調用內部的，如果條件。

// You'll want to start with getPermutionsR(v, n, 0, 0, 1) 
void getPermutationsR(int v[], int n, int i, int j, bool firstCall) 
{ 
    if (i == n) 
    { 
     //Display contents of v 
    } 

    int x = i; 
    int y = j+1; 
    if (firstCall) { 
     swap (v, i, j); 
     x = i+1; 
     y = i+1; 
    } 

    // My one recursive call. Note that i=n implies j=n. 
    if (j < n) { 
     getPermutationsR(v, n, x, y, !firstCall); 
    } 

    if (firstCall) { 
     swap (v, i, j); 
    } 
} 

既然我們已經完成了這一步，我們可以通過一種可以直接轉換爲迭代版本的形式。這裏是改造

void recursiveForm (params, recursiveState) { 
    topHalf... 
    if (cond) { 
     recursiveForm(...) 
    } 
    bottomHalf... 
} 

成爲

void iterativeForm(params) { 
    initializeStacks... 
    pushStacks... 
    topHalf... 
    while (stacks not empty) { 
     if (cond) { 
      pushStacks... 
      topHalf... 
     } 
     else { 
      bottomHalf... 
      popStacks... 
     } 
    } 
} 

因此應用此模式，我們得到如下：

// You'll want to start with getPermutionsR(v, n, 0, 0, 1) 
void getPermutationsI(int v[], int n) 
{ 
    stack<int> iStack; 
    stack<int> jStack; 
    stack<bool> firstCallStack; 

    // pushStacks with initial value 
    iStack.push(0); 
    jStack.push(0); 
    firstCallStack.push(1); 

    // topHalf... 
    if (iStack.top() == n) 
    { 
     //Display contents of v 
    } 

    int x = iStack.top(); 
    int y = jStack.top()+1; 
    if (firstCallStack.top()) { 
     swap (v, iStack.top(), jStack.top()); 
     x = iStack.top()+1; 
     y = iStack.top()+1; 
    } 

    while iStack.size() > 0) { 
     // if (cond) { 
     if (jStack.top() < n) { 
      //pushStacks... 
      iStack.push(x); 
      jStack.push(y); 
      firstCallStack.push(!firstCallStack.top()); 

      // topHalf... 
      if (iStack.top() == n) 
      { 
       //Display contents of v 
      } 

      x = iStack.top(); 
      y = jStack.top()+1; 
      if (firstCallStack.top()) { 
       swap (v, iStack.top(), jStack.top()); 
       x = iStack.top()+1; 
       y = iStack.top()+1; 
      } 
     } 
     else { 
      // bottomHalf... 
      if (firstCallStack.top()) { 
       swap (v, iStack.top(), jStack.top()); 
      } 
     } 
    } 
} 

（警告，所有的測試的代碼，而且可能甚至不會編譯但這個想法是正確的，而且它絕對是相同的算法。）

Answer 2

您需要閱讀TAOCP的章節7.2.1.2。

---

編輯：
根據該意見的討論中，一個基於堆棧的遞歸消除也好（雖然在我看來，它不是一個純粹的迭代方法）。 這裏是一個基於堆棧的版本的草案：

void getPermutationsNR(int v[]) 
{ 
    struct task 
    { 
     enum { swap, reccall } tasktype; 
     int i, j; 
    } 
    stack<task> stack; 
    stack.push(new task() {tasktype=reccall, i=0}); // initial task 
    while (!stack.empty) // run task interpreter 
    { 
     task t = stack.pop(); 
     switch (t.tasktype) 
     { 
      case reccall: 
      if (t.i == n) {/*display contents*/; break;} 
      for (int j=t.i; j<n; j++) 
      { 
       stack.push(new task() {tasktype=swap, t.i, j}); 
       stack.push(new task() {tasktype=reccall, t.i+1}); 
       stack.push(new task() {tasktype=swap, t.i, j}); 
      } 
      break; 
      case swap: 
      swap(v, t.i, t.j); 
      break; 
     } 
    } 
} 

Answer 3

您可以使用STL：

a[]={0,1,2,....n-1}; 
do{ 
    for(int i=0;i<n;++i) 
     // print v[ a[i] ] 
    //print EOLN 
} 
while(next_permutation(a,a+n)); 

未經測試。

Answer 4

您可以使用堆棧來迭代。在這個棧中，你存儲你的變量j。這應該工作。

void getPermutationsI(int v[], int n) 
{ 
    int stack[100] = {0, 1, 2, 3, 4}; // you can do better, but I was lazy 
    int k = 0; 
    while (k >= 0) 
    { 
     if (k == n) 
     { 
      for (int i = 0; i < n; ++i) 
       printf("%d ", v[i]); 
      printf("\n"); 

      --k; 
      swap(v[k], v[ stack[k] - 1 ]); 
     } 
     else 
     { 
      if (stack[k] < n) 
      { 
       swap(v[k], v[ stack[k] ]); 
       ++stack[k]; 
       ++k; 
      } 
      else 
      { 
       stack[k] = k; 
       --k; 
       swap(v[k], v[ stack[k] - 1 ]); 
      } 
     } 
    } 
} 

Answer 5

在Python中：

def perm_stack(s): 
    st = [] 

    st.append((s,0)) 

    while not len(st)==0: 

     t = st.pop() 
     if t[1]==len(s): 
      print t[0] 
     else: 
      for i in range(t[1], len(s)): 
       s1 = swap(t[0], t[1], i) 
       st.append((s1, t[1]+1))