Преобразование генератора рекурсивной перестановки в итеративный

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);
    }
}

Далее давайте добавим больше состояния, чтобы у нас был только один рекурсивный вызов внутри условия if.

// 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

Вы можете использовать стек, чтобы сделать его итеративным. В этом стеке вы храните переменную 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 3

В 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))

Answer 4

Вы можете использовать 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 5

Вам необходимо прочитать главу 7.2.1.2 TAOCP .

---

EDIT:
Согласно обсуждению в комментариях, устранение рекурсии на основе стека также хорошо (хотя, на мой взгляд, это не чисто итеративный подход). Вот черновик стековой версии:

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;
        }
    }
}