作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

最近一直在看<<C++标准程序库>>这本书，在看到"变序性算法"部分的时候，发现两个函数next_permutation, prev_permutation对于我们平时处理排列组合的问题很有帮助，根据书上的介绍写了两个个测试函数:
void func1()
{
    vector<int> v;

    INSERT_ELEMENTS(v, 1,3);

    PRINT_ELEMENTS( v, "myself: ");
 
    while( next_permutation( v.begin(), v.end() ) )
    {
 
        PRINT_ELEMENTS( v, "");
    }
}

void func2()
{
    vector<int> v;

    INSERT_ELEMENTS(v, 1,3);

    PRINT_ELEMENTS( v, "myself: ");
 
    while( prev_permutation( v.begin(), v.end() ) )
    {
 
        PRINT_ELEMENTS( v, "");
    }
}

结果运行的时候发现func1输出的结果是正确的:
myself: 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

但func2输出的结果却是这样:
myself: 1 2 3

再仔细看看书上的说明，终于发现了出错的原因了:
书上其实写的很清楚的: "如果要走遍所有的排列，你必须先将元素排序"

于是修改func2如下:
void func2()
{
    vector<int> v;

    INSERT_ELEMENTS(v, 1,3);

    PRINT_ELEMENTS( v, "myself: ");

    sort(v.begin(), v.end(), greater<int>() ); //增加排序(降序)
 
    while( prev_permutation( v.begin(), v.end() ) )
    {
 
        PRINT_ELEMENTS( v, "");
    }
}
输出的结果正确了 ^_^

相关软件：