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