#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;
}