E*******0
发帖数: 465 | 1 我说下我的算法，大家帮忙看看有没有问题。
#include
class Solution {
public:
void nextPermutation(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (1==num.size())
return;
vector::reverse_iterator rit;
vector::reverse_iterator it1,it2;
for ( rit=num.rbegin() ; rit < num.rend(); ++rit )
{
rit++;
it1=rit;
rit--;
it2=rit;
if ((*(it2))>(*(it1)))
{
for (;it2!=num.rbegin();it2--)
if((*it1)>(*it2))
break;
it2--;
int temp=*it2;
*it2=*it1;
*it1=temp;
it1--;
sort(it1,num.end());
}
}
}
}; |
E*******0
发帖数: 465 | 2 我的基本想法是
1 2 3 4 5 6
- 从vector的最后一个开始循环，两个指针it1, it2分别指向当前循环指针和之前一个。
for example, 一开始it1指向6，it2 指向5.
- 比较这两个数
a) it1 >= it2 继续循环。这样可以保证所有在it1之后的书是逆序排列。
b) it1 < it2,把it1 to end 中第一个比it2大的数找到，和it2环位置，并且把从
it1 to end的数顺序排列。
- 直到所有的数都是逆序排列。 |
E*******0
发帖数: 465 | 3 举个例子
1 2 3 4 5 6
找出 4 6 5 3 2 1的next permutation.
it1 -> 6 it2 ->4 since 6 5 3 2 1是逆序排列。
找出 it1 to end 中第一个比4大的数5，（note:这里第一个币it2大的数，不是位置，
是大小上第一个比it2大的数）把5和4位置换一下。
5 6 4 3 2 1 在把6 to end 顺序排列。
so next permutation是 5 1 2 3 4 6。 |
r*****e
发帖数: 792 | 4 先说说你什么思想吧？我也刚刚写了一个，是返回bool的，好像比你的要复杂。
我的思路是从最后一位数起往前找到第一个位置i，s.t. vector[i]
sort 从i+1 to end（）, 然后swap vector[i] 和sort的range里第一个比
vector[i]大的。
也想先听听你的思路是什么，看看是不是更简单。
【在 E*******0 的大作中提到】
: 我说下我的算法，大家帮忙看看有没有问题。
: #include
: class Solution {
: public:
: void nextPermutation(vector &num) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: if (1==num.size())
: return;
: vector::reverse_iterator rit;
|
N*****8
发帖数: 253 | 5 1). 从右往左找第一个a[i-1] < a[i]的，记i-1为index1；
2). 从右往左找第一个比a[index1]大的数，记index2;
3). swap(a, index1, index2);
4). reverse(a, index+1, a.length-1) |
r*****e
发帖数: 792 | 6 最后一步应该是sort吧？
【在 N*****8 的大作中提到】
: 1). 从右往左找第一个a[i-1] < a[i]的，记i-1为index1；
: 2). 从右往左找第一个比a[index1]大的数，记index2;
: 3). swap(a, index1, index2);
: 4). reverse(a, index+1, a.length-1)
|
E*******0
发帖数: 465 | 7 我的基本想法是
1 2 3 4 5 6
- 从vector的最后一个开始循环，两个指针it1, it2分别指向当前循环指针和之前一个。
for example, 一开始it1指向6，it2 指向5.
- 比较这两个数
a) it1 >= it2 继续循环。这样可以保证所有在it1之后的书是逆序排列。
b) it1 < it2,把it1 to end 中第一个比it2大的数找到，和it2环位置，并且把从
it1 to end的数顺序排列。
- 直到所有的数都是逆序排列。
【在 r*****e 的大作中提到】
: 先说说你什么思想吧？我也刚刚写了一个，是返回bool的，好像比你的要复杂。
: 我的思路是从最后一位数起往前找到第一个位置i，s.t. vector[i]: sort 从i+1 to end（）, 然后swap vector[i] 和sort的range里第一个比
: vector[i]大的。
: 也想先听听你的思路是什么，看看是不是更简单。
|
E*******0
发帖数: 465 | 8 我的思路和你一样。
【在 N*****8 的大作中提到】
: 1). 从右往左找第一个a[i-1] < a[i]的，记i-1为index1；
: 2). 从右往左找第一个比a[index1]大的数，记index2;
: 3). swap(a, index1, index2);
: 4). reverse(a, index+1, a.length-1)
|
N*****8
发帖数: 253 | 9 index1+1:a.length-1本来就是一个逆序的子数组了，不用sort，reverse就是最小的子
数组组合。
【在 r*****e 的大作中提到】
: 最后一步应该是sort吧？
|
d***i
发帖数: 344 | 10 之前的遍历保证pivot后面是增序，reverse就够了。
不过这样做有个catch：做swap的时候要从右往左找。如638551。3要跟右起第一个5换
，不能跟第二个5换；不然reverse的结果错误。
从右边找这点人已经写在算法里了，我只是强调一下，呵呵
【在 r*****e 的大作中提到】
: 最后一步应该是sort吧？
|
|
|
r*****e
发帖数: 792 | 11 yes, you are right
【在 N*****8 的大作中提到】
: index1+1:a.length-1本来就是一个逆序的子数组了，不用sort，reverse就是最小的子
: 数组组合。
|
r*****e
发帖数: 792 | 12 for 2), if use binary search, it would look nicer even though
overall complexity is not affected.
【在 N*****8 的大作中提到】
: 1). 从右往左找第一个a[i-1] < a[i]的，记i-1为index1；
: 2). 从右往左找第一个比a[index1]大的数，记index2;
: 3). swap(a, index1, index2);
: 4). reverse(a, index+1, a.length-1)
|
E*******0
发帖数: 465 | 13 // NextPermutation.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
using namespace std;
#include
bool myfunction (int i,int j) { return (i>j); }
bool nextPermutation(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//If vector size is 1, permutation is its self.
if (1==num.size())
return true;
// rit is the iterator indicates current item;
// it1 is the iterator indicates left of current item;
// it2 is the iterator indicates the first item bigger than it1;
// it3 temp iterator.
vector::reverse_iterator rit, it1,it2,it3;
for ( rit=num.rbegin() ; rit < num.rend(); ++rit )
{
it1=++rit;
// If the current item is the leftmost item, this is the last
permutation.
if (it1==num.rend())
return false;
it1=rit;
// it3 indicates current item; it1 indicates left of current item.
it3=--rit;
// If it1 < it3, get the first bigger item from it3 to end.
if (*it3>*it1)
{
for (it3=it3;it3>num.rbegin();it3--)
//it3 indicates the first item smaller than it1. So the left
of current it3 is the first bigger items of it1.
if(*it1>*it3)
{
++it3;
break;
}
if (it3==num.rbegin())
if (*it1>*it3)
{
++it3;
}
// Another case is if all the items after it1 is bigger than it1
, the first bigger item is the rightmost one. No need ++it3.
int temp=*it3;
*it3=*it1;
*it1=temp;
sort(num.rbegin(),it1,myfunction);
break;
}
}
return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
vector *num=new vector();
(*num).push_back(1);
(*num).push_back(2);
(*num).push_back(3);
(*num).push_back(4);
//(*num).push_back(5);
//(*num).push_back(6);
while(nextPermutation(*num))
{
for (vector::iterator it=(*num).begin();it!=(*num).end();it++)
cout << (*it) << " ";
cout << endl;
}
return 0;
} |
E*******0
发帖数: 465 | 14 output is
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1 |
E*******0
发帖数: 465 | 15 终于调试成功了。
对vector iterator不熟悉。
有几个STL的问题问一下：
1）如何将reverse_iterator convert to iterator?
2) 大家在for 循环时，都怎么保证访问到最后一个元素？
for (reverse_iterator it=it.rend; it
这样的话，不可以访问到最后一个元素，因为rbegin indicates the last element. |
h**********l
发帖数: 6342 | 16 用ritr 也是＋＋
【在 E*******0 的大作中提到】
: 终于调试成功了。
: 对vector iterator不熟悉。
: 有几个STL的问题问一下：
: 1）如何将reverse_iterator convert to iterator?
: 2) 大家在for 循环时，都怎么保证访问到最后一个元素？
: for (reverse_iterator it=it.rend; it: 这样的话，不可以访问到最后一个元素，因为rbegin indicates the last element.
|
E*******0
发帖数: 465 | |
h**********l
发帖数: 6342 | 18 那你这么用 r 的好处是啥？ 为啥不直接用正的？
【在 E*******0 的大作中提到】
: 我从rend开始的，到rbegin应该是--
|
E*******0
发帖数: 465 | 19 我不知道怎么把r_iterator convert to iterator |
E*******0
发帖数: 465 | 20 因为之前是reverse循环，我用了r_iterator，并且把它付给下个for循环，本来想用
iterator的，不知道怎么转换。 |
E*******0
发帖数: 465 | 21 因为之前是reverse循环，我用了r_iterator，并且把它付给下个for循环，本来想用
iterator的，不知道怎么转换。 |
E*******0
发帖数: 465 | 22 I just found we can use it=rit.base() to get the iterator from reverse_
iterator.
Share with you guys. Thanks, |
