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
101
102
103
104
105
106
107
108


#include <vector>
#include <iostream>

using namespace std;

int BSearchUpperbond(vector<int> & array, int low, int high, int target)
{
    if (high< low || 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;
}

void ReverseArray(vector<int> & array, int low, int high)
{
    while(low < high)
    {
        int temp = array[low];
        array[low++] = array[high];
        array[high--] = temp;
    }
}



bool NextPermutation(vector<int> & array)
{
    int size = array.size()-1;
    int back = size;

    while(--back >= 0 && array[back] >= array[back+1]);

    ReverseArray(array, back+1, size);

    if (back >= 0)
    {
        int index = BSearchUpperbond(array, back+1, size, array[back]);
        int temp = array[index];
        array[index] = array[back];
        array[back] = temp;

        return true;
    }

    return false;
}


void PrintVector(vector<int> & array)
{
    for (int i = 0; i < array.size(); ++i)
        cout<< array[i] << ',';
    cout << endl;
}


int main(int argc, char** argv)
{
    vector<int> v;
    cout << "test1:\n";

    for (int i = 1; i < 8; ++i)
	       v.push_back(i);
    vector<int> saved = v;
    do
    {
        PrintVector(v);
        NextPermutation(v);
    }while(v != saved);

    cout << "\n\ntest2:\n";
    v.clear();
    v.push_back(1);
    v.push_back(1);
    v.push_back(2);
    saved = v;
    do
    {
        PrintVector(v);
        NextPermutation(v);
    }while(v != saved);

    //If the array is alrealy sorted ascendingly, following codes works better
    // do
    // {
    //     PrintVector(v);
    // }while(NextPermutation(v));

    return 0;
}






View Program Text


Test Status