[面试] 全排列（非递归）

打印一个数组的全排列，要求非递归。

模拟递归当然会想到用栈模拟，最主要的是考虑初始的压入栈中的值，这里首先想到递归调用是用一个for循环遍历0到n-1的索引，看哪个可以用（比如k)就递归调用函数，然后返回的时候在k+1继续循环查找下去。这里的关键是如何能模拟循环的一个过程，于是我考虑到用出栈的值的下一个值来继续for循环的下一个值，于是初始从0开始，我们就可以先压入-1，然后再把它弹出栈，取下一个值作为for循环的初始值。然后当栈大小>n时打印。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void permutation(int a[], int n)
{
    vector<int> b(n);
    vector<bool> canUse(n);

    for(int i = 0; i < n; i++)
        canUse[i] = true;

    stack<int> s;

    s.push(-1);

    while(!s.empty())
    {
        if (s.size() > n)
        {
            for(int i = 0; i < n; i++)
                cout << b[i] << ' ';
            cout << endl;
            s.pop();
            continue;
        }

        if (s.top() >= 0)
            canUse[s.top()] = true;

        int start = s.top() + 1;
        s.pop();
        for(int i = start; i < n; i++)
            if (canUse[i])
            {
                canUse[i] = false;
                b[s.size()] = a[i];
                s.push(i);
                s.push(-1);
                break;
            }
    }
}

int main()
{
    int a[] = {1, 2, 3};

    int aSize = sizeof(a) / sizeof(int);

    permutation(a, aSize);
}