1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100


/*
** The C++ <algorithm> has method named: next_permutation(),
** it is nice to validate our program with this method
**
** To solve this problem, we just need 3 steps:
** 1. search from bottom to top, find the first place where the element(say A) is not decreasely,
** 2. sort the elements after A increasely,
** 3. replace the A with element which is just larger than A in the array after A.
**
*/
#include <vector> using namespace std; void Swap(int& a, int& b) { int temp = a; a = b; b = temp; } //find first element that is larger than target in array which range is [low, high] int BSearchUpper(vector<int>& array, int low, int high, int target) { if (low > high || array[high] < target) return -1; int mid = (low + high) / 2; while(low < high) { if (array[mid] <= target) low = mid + 1; else high = mid; mid = (low + high) / 2; } return mid; } //reverse the array elements range in [low, high] void ReverseArray(vector<int>& array, int low, int high) { while(low < high) { //swap two elements Swap(array[low], array[high]); ++ low; -- high; } } void NextPermutation(vector<int> &array) { int length = array.size()-1; int i = array.size(); while(--i > 0 && array[i-1] >= array [i]); ReverseArray(array,i,length); //if array is last permutation, we just reverse array, //otherwise, swap the elements with the one that is just larger than it if (i >= 0) { int upper = BSearchUpper(array,i,length, array[i-1]); Swap(array[i-1], array[upper]); } } #include <iostream> using namespace std; template<typename T> void PrintVector(T v, size_t size) { for (size_t i = 0; i < size; ++i) cout << v[i]<<", "; cout << endl; } int main(int argc, char** argv) { vector<int> v; v.push_back(3); v.push_back(4); v.push_back(1); v.push_back(2); PrintVector(v,4); NextPermutation(v); PrintVector(v,4); return 0; }
View Program Text


Test Status