Johnson-Trotter算法生成全排列

2016年01月04日 原创
关键词: C++ 数据结构 算法
摘要 Johnson-Trotter算法生成全排列的时间复杂度为O(n!),是最快的生成全排列的算法之一。

从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。生成全排列的时间复杂度从理论上来说的最优复杂度也是O(n!),因为一共要生成n!个排列。下面介绍的Johnson-Trotter算法就是生成全排列的算法中最快的算法之一。

以下是该算法的描述:

算法      JohnsonTrotter(n)
 //实现用来生成排列的Johnson-Trotter算法
 //输入:一个正整数n
 //输出:{1,...n}的所有排列的列表
 //将第一个排列初始化为 12  3  ... n
    while  存在一个可以移动的元素k  do

       求最大的移动元素k

       把k和它方向所指的相邻元素互换

       调转所有大于k的元素的方向

       将新排列添加到列表

其中对于一个元素m是否可以移动,是这样判断的:

        如果该元素位于第一个数的位置并且方向向左,则不能移动

        如果该元素位于最后一个数的位置并且方向向右,则不能移动

        如果该元素大于要移动方向的相邻元素,则可以移动;否则不能移动

对于n=3应用该算法,其中最大的移动整数用粗体字表示:

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3


下面是该算法的c++代码:

#include<iostream>
#include<vector>
using namespace std;
class element{
public:
    int num;
    int direction = left;
    static const int left = 0;
    static const int right = 1;
    element(int num) :num(num){}
};
void print(vector<element> elements) {
    for (vector<element>::iterator iter = elements.begin(); iter != elements.end(); iter++) {
        cout << iter->num << " ";
    }
    cout << endl;
}

bool canMove(vector<element> elements) {
    for (int i = 0; i < elements.size(); i++) {
        if (elements[i].direction == element::right) {
            if (i != elements.size() - 1 && elements[i].num > elements[i + 1].num)
                return true;
        }
        else {
            if (i != 0 && elements[i].num > elements[i - 1].num) {
                return true;
            }
        }
    }
    return false;
}
void moveElement(vector<element>& elements) {
    int pos = 0;
    int term = 0;
    for (int i = 0; i < elements.size(); i++) {
        if (elements[i].direction == element::right) {
            if (i != elements.size() - 1 && elements[i].num > elements[i + 1].num) {
                if (term<elements[i].num){
                    term = elements[i].num;
                    pos = i;
                }
            }

        }
        else {
            if (i != 0 && elements[i].num > elements[i - 1].num) {
                if (term < elements[i].num) {
                    term = elements[i].num;
                    pos = i;
                }
            }

        }
    }

    if (elements[pos].direction == element::left) {
        swap(elements[pos], elements[pos - 1]);
    }
    else {
        swap(elements[pos], elements[pos + 1]);
    }
    for (vector<element>::iterator iter = elements.begin(); iter != elements.end(); iter++) {
        if (iter->num > term) {
            iter->direction = iter->direction == element::left ? element::right : element::left;
        }
    }
}

void JohnsonTrotter(int n) {
    vector<element> elements;
    for (int i = 1; i <= n; i++) {
        elements.push_back(element(i));
    }
    print(elements);
    while (canMove(elements)) {
        moveElement(elements);
        print(elements);
    }

}
int main() {
    JohnsonTrotter(4);
    return 0;
}

下面是n=3和n=4的时候的运行结果

n=3:

n=4: