基于栈的无递归字符串全排列：State结构体place字段解析

我写了一段用栈实现无递归字符串全排列的C++代码，但搞不懂State结构体里place字段的作用，以及它在算法逻辑里的具体角色。我自己定义了只包含word和next的Node类，想知道为什么必须要有place字段。

我的全排列实现代码如下：

struct State
{
    State (std::string topermute_, int place_, int nextchar_, State* next_ = 0)
        : topermute (topermute_)
        , place (place_)
        , nextchar (nextchar_)
        , next (next_)
    {
    }

    std::string topermute;
    int place;
    int nextchar;

    State* next;
};

std::string swtch (std::string topermute, int x, int y)
{
    std::string newstring = topermute;
    newstring[x] = newstring[y];
    newstring[y] = topermute[x]; //avoids temp variable

    return newstring;
}

void permute (std::string topermute, int place = 0)
{
    // Linked list stack.
    State* top = new State (topermute, place, place);

    while (top != 0)
    {
        State* pop = top;
        top = pop->next;

        if (pop->place == pop->topermute.length () - 1)
        {
            std::cout << pop->topermute << std::endl;
        }

        for (int i = pop->place; i < pop->topermute.length (); ++i)
        {
            top = new State (swtch (pop->topermute, pop->place, i), pop->place + 1, i, top);
        }

        delete pop;
    }
}

int main (int argc, char* argv[])
{
    if (argc!=2)    
    {
        std::cout<<"Proper input is 'permute string'";
        return 1;
    }
    else
    {
        permute (argv[1]);
    }

    return 0;
}

我自己定义的Node类代码：

class Node
{
    public:
        string word; // stores the word in the node
        Node *next;
};

为什么需要place字段？ #

这个place字段是用来标记当前排列操作的进度的，对应递归实现全排列里的「当前固定的位置」。

先回忆递归全排列的逻辑：

递归版全排列的核心思路是：

• 固定第place个位置的字符（把后面每个字符和它交换）
• 递归处理place+1位置开始的子串
• 当place等于字符串长度-1时，说明已经固定了所有位置，得到一个完整排列

无递归用栈模拟时的需求：

栈里的每个元素需要保存「当前处理到哪一步」的状态，不然只存字符串的话，你根本不知道接下来要对这个字符串做什么操作——是要继续固定下一个位置，还是已经到了输出的时候？

比如，当你从栈里取出一个字符串"bac"，如果没有place字段，你没法判断：

• 是不是已经到了最后一个位置（要不要输出）
• 接下来应该从哪个位置开始交换字符，生成下一层的排列

具体看代码里的作用：

1. 终止条件判断：if (pop->place == pop->topermute.length () - 1)——当place是最后一个索引时，说明这个字符串已经是完整排列，直接输出。
2. 生成下一层状态：循环里swtch(pop->topermute, pop->place, i)是把当前place位置的字符和后面的i位置交换，然后新状态的place设为pop->place + 1，表示接下来要处理下一个位置的固定。

你的Node类为什么不够？

你的Node类只存了word和链表指针，缺少了当前处理进度的信息。这样从栈里取出一个Node时，你不知道这个字符串是处于排列的哪一步：是刚处理到第0位，还是第2位？也就没法正确生成下一层的排列状态，也没法判断是否要输出结果。

内容的提问来源于stack exchange，提问作者beginnerprogrammer