非递归实现全排列_全排列无递归

非递归实现全排列

要求：使用非递归的方法按照字典序输出全排列

思路：

1. 不让递归的话，只能通过上一个排列通过特殊的方法推算出来下一个排列
2. 这次以“1 5 4 3 2”为例，下一个排列是“2 1 3 4 5”
3. 从后往前找，找到第一个连续递增的两个数字，找到了“1 5”
4. 重新从后往前找，找到第一个大于“1”的数字，找到了“2”，“1”就是步骤三中找到的第一个数字
5. 找到“2”之后，将“1”和“2”互换，换成了“2 5 4 3 1”
6. 然后将“5”后面的全部数字翻转（包括“5”），“5”就是步骤三找到的第二个数字，变成了“2 1 3 4 5”，完事

代码实现：

int main(int argc, char* argv[]) {
  int n = 5;
  vector<int>s;
  for (int i = 1; i <= n; i++)
    s.push_back(i);
  //以上都是初始化的操作
  //其中，n代表n个数字全排列，s用来存储最开始的答案

  int len = s.size();
  while (true) {
    print(s);//打印s数组，自己写一个
    if (len < 2) break;//如果只有一个元素，就直接退出
    int i, j;
    for (i = len - 1; i > 0; i--)
      if (s[i - 1] < s[i]) break;//步骤三
    if (i == 0)break;//判断是否到头
    for (j = len - 1; j > i; j--)
      if (s[i - 1] < s[j]) break;//步骤四
    swap(s[j], s[i - 1]);//步骤五
    reverse(s.begin() + i, s.end());//步骤六
  }
  //每次操作之后，都不必恢复，因为原理是找当前排列的下一个排列
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

如果需要逆序输出

1. 将初始数组置为正序的最后一个排列（5 4 3 2 1）
2. 将步骤三四的小于改为大于即可。

因为5的全排列太多了，所以这里是4的全排列
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1