简介

给定一个 N 元组，我们称一个这样的 N 维向量：

$$ (i_1, i_2, \cdots, i_N) $$

是它的一个 permutation, 其中所有的这些 i 都是 [0,N) 范围内的整数，并且没有重复。

举例：给定 N=4, 以下都是 N=4 的 permutation:

(0,1,2,3), (0,1,3,2), (0,2,1,3), (0,2,3,1),(0,3,1,2),(0,3,2,1),(1,0,2,3),(1,0,3,2),(1,2,0,3),(1,2,3,0),(1,3,0,2),(1,3,2,0), …

N = 4 的 permutations 总共有 4! = 24 个。

一个 N 元组的 permutation 描述的是对一个 N 元 tuple 进行的排列操作，容易验证，一个 4 元组有 4! = 24 种排列方式。

生成 N 元 permutations 的代码

给定 n, 以下代码以（平均）O(n) 的空间复杂度，和 O(n!) 的时间复杂度生成所有 n 元 permutations:

#include <iostream>
#include <vector>

struct Node {
    Node( ) : idx(-1), next(nullptr) {}
    explicit Node(int idx) : idx(idx), next(nullptr) {}
    int idx;
    Node *next;
};

void traverse_perm(Node *head, Node *last, std::vector<int>& trace) {
    if (head == last) {
        for (auto && elem : trace) {
            std::cout << elem << " ";
        }
        std::cout << head->idx << std::endl;
        return;
    }

    Node *prev = last;
    Node *x = head;
    while (true) {
        Node *tmp = prev->next;
        prev->next = x->next;
        trace.push_back(x->idx);
        traverse_perm(x->next, prev, trace);
        trace.pop_back();
        prev->next = tmp;
        prev = x;
        if (x == last) {
            break;
        }
        x = x->next;
    }
}

void print_permutations(int n) {
    Node dummy;
    Node *head = &dummy;
    Node *last;
    for (int i = 0; i < n; ++i) {
        head->next = new Node(i);
        head = head->next;
        last = head;
    }

    std::vector<int> trace;
    last->next = dummy.next;
    traverse_perm(dummy.next, last, trace);

    last->next = nullptr;
    head = dummy.next;
    while (head) {
        Node *next = head->next;
        delete head;
        head = next;
    }
}

// Example usage: print all n=4 permutations to stdout.
int main() {  
  print_permutations(4); 
  return 0;
}

这段代码执行时将所有 n=4 的 permutations 逐行打印到标准输出中。

我们可以对上列代码做一些重构，以增加代码的可读性和可复用性，首先，把辅助链表的构造和销毁过程都抽象为专用的函数：

void build_linked_list(int n, Node **head, Node **last) {
    Node dummy;
    Node *h = &dummy;
    Node *l;
    for (int i = 0; i < n; ++i) {
        h->next = new Node(i);
        h = h->next;
        l = h;
    }
    *head = dummy.next;
    *last = l;
}

void free_linked_list(Node *head) {
    while (head) {
        Node *next = head->next;
        delete head;
        head = next;
    }
}

然后，我们注意到原函数中存在一个（递归地）遍历链表每一个节点以及与该节点对应的剩余链表的过程，这个过程也可以抽象成一个通用的函数，从而支持调用者自定义任意的访问行为（ visitor pattern）：

void traverse_linked_list(Node *head, Node *last, std::function<void (Node *curr, Node *rest_head, Node *rest_tail)> action) {
    Node *prev = last;
    Node *curr = head;
    while (true) {
        Node *tmp = prev->next;
        prev->next = curr->next;

        // call with current node and the remainder list.
        action(curr, curr->next, prev);

        prev->next = tmp;
        prev = curr;

        if (curr == last) {
            break;
        }
        curr = curr->next;
    }
}

action 函数在每轮迭代中被以一个当前节点，剩余链表的首节点和尾节点（指针）三个参数调用。

至于递归，为了通用性，则不是我们在实现 traverse_linked_list 时应当考虑的事，应该交由调用者自己负责实现。

进行了这些抽象之后，traverse_perm 函数变成这样：

void traverse_perm(Node *head, Node *last, std::vector<int> &trace) {
    auto action = [&trace](Node *curr, Node *rest_head, Node *rest_tail) -> void {
        trace.push_back(curr->idx);

        if (rest_head != rest_tail) {
            traverse_perm(rest_head, rest_tail, trace);
        } else {
            for (auto && elem : trace) {
                std::cout << elem << " ";
            }
            std::cout << rest_head->idx << std::endl;
        }

        trace.pop_back();
    };
    traverse_linked_list(head, last, action);
}