/* Sap xep n nguoi vào 1 bàn tròn, Valkirie code */
#include <iostream>
#include <iomanip>

const int array_size = 10;
int n, index;

void insert_item_into_array(int numbers[array_size], int size,  int item, int position )
{
        for (int i = size; i > position; i--)
        {
                numbers[i] = numbers[i-1];
        }
        numbers[position] = item;
}

void print( int numbers[array_size], int size )
{

        index++;
        cout << "Cach sap xep thu " << index << "\n\t";
        for (int i = 0; i < size; i++)
        {
                cout << setw(3) << numbers[i] + 1;
        }
        cout << endl; cin.get();
}

void swap ( int &first_num, int &second_num )
{
        int temp = first_num;
        first_num = second_num;
        second_num = temp;
}

void insert( int numbers[array_size], int step )
{
        // Neu da chen du so nguoi thi in ket qua ra va tro ve trang thai truoc do
        if (step >= n )
        {
                print( numbers, step);
                return; // thay cho if else, return chõ này là out khoi hàm.
        }

        int temp[array_size];
        // luu mang number lai
        for ( int i = 0; i <= step; i++ ) temp[i] = numbers[i];
        
        int position = step;                
        insert_item_into_array( numbers, step, step, position );
        do
        {
                // chuyen sang xet trang thai (step+1) voi mang numbers gom step + 1 so
                insert( numbers, step +1 );
                if (position > 1)
                {
                        swap( numbers[position-1], numbers[position]);
                }
                position--;
        }
        while (position >= 1);
        // phuc hoi mãng 
        for ( i = 0; i <= step; i++ ) numbers[i] = temp[i];
}

void main()
{
        int numbers[array_size];
        cout << "Moi ban nhap so nguoi, n > 3: "; cin >> n;

        for ( int i = 0; i < 3; i++ )
                numbers[i] = i;
        
        index = 0;
        insert(numbers ,3);
}