算法:全排里问题——邻位互换法

邻位互换法,只要你在学全排列就不可不学的一个及其有趣的算法。

例题

洛谷1706 全排列问题

题目描述
按照邻位互换法的顺序输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

输入格式
一个整数n。

输出格式
由1~n组成的所有不重复的数字序列,每行一个序列。
每个数字保留 5个场宽。

输入样例

3

输出样例

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

全排列问题——邻位互换法

邻位互换法其实是一个比较容易理解的算法,这里我们需要定义一个概念:如果说一个数比它指针所指向的数小,它就处于活动状态,当然所指向的数不能越界。此时,你可能会问这个指针是啥,其实这个指针只能指向他的下一个数或者上一个数,比如a[i]的指针只能指向a[i - 1]或者a[i + 1]。这个指针我们就用face[i]来记录:当face[i] = 1时,表示a[i]指向a[i + 1];当face[i] = -1时,表示a[i]指向a[i - 1]。这样使用起来也很方便,比如我要去找a[i]的指向位置,直接就是a[i + face[i]],不用再去if判断了。

引入这个概念之后,我们就具体来说步骤了:

  1. 初始化全排列1, 2, 3,…… ,n。
  2. 将指针都指向左侧,即face[i] = -1。
  3. 从a[1] ~ a[n]中找出处于活动状态的最大值的位置pos。
  4. 如果没有一个处于活动状态的数,代表所有的全排列已经生成完毕。
  5. 交换a[pos]和其指向的数a[pos_to]。pos_to就是a[pos]指向的位置,即pos + face[pos]。
  6. 交换face[pos]和face[pos_to]。这步千万不要忘!
  7. 在排列中将所有的大于a[pos_to]的数的face都取反。这里一定时a[pos_to]因为我们已经交换了a[pos]和a[pos_to]。
  8. 不停地循环重复步骤3、4、5、6、7,每次执行完一次就进行输出,直到4步骤返回false,结束。

最后,算一下算法的时间复杂度:每次求下一个排列仅n次即可,共有n!的全排列,所以总时间复杂度为O(n * n!)。

代码

# include <cstdio>
# include <algorithm>
# include <cstring>
# include <cmath>

using namespace std;

const int N_MAX = 10;

int n;
int a[N_MAX + 10];
int face[N_MAX + 10];

bool canMove(int x)
{
    int y = x + face[x];
    return y >= 1 && y <= n && a[x] > a[y];
}

bool permutation()
{
    int a_max = 0, pos = -1;
    for (int i = 1; i <= n; i++) {
        if (!canMove(i) || a_max > a[i]) continue;
        a_max = a[i], pos = i;
    }
    if (pos == -1) return false;
    int pos_to = pos + face[pos];
    swap(a[pos], a[pos_to]);
    swap(face[pos], face[pos_to]);
    for (int i = 1; i <= n; i++)
        if (a[i] > a_max) face[i] = -face[i];
    return true;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        a[i] = i;
    memset(face, -1, sizeof(face));
    do {
        for (int i = 1; i <= n; i++)
            printf("%5d", a[i]);
        printf("\n");
    } while (permutation());
    return 0;
}
上一篇:springboot项目通过本地引入第三方jar包时,第三方jar包无法打包进项目


下一篇:mysql事务的实现原理