关于STL中使用next_permutation, prev_permutation实现排列组合的问题

[入库:2005年8月18日] [更新:2007年3月24日]

本文简介:选择自 hydnoahark 的 blog

最近一直在看<<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, "");
    }
}
输出的结果正确了 ^_^

 

本文关键:STL, 排列组合, next_permutation, prev_permutation
  相关方案
Google
 

本站最佳浏览方式为 分辨率 1024x768 IE 6.0(或更高版本的 IE浏览器)

go top