#include <cstdlib>
#include <iostream>
#include <ctime>

int main();
unsigned int *choose( unsigned int n, unsigned int k );

unsigned int *choose( unsigned int n, unsigned int k ) {
    unsigned int *array = new unsigned int[k];

    for ( unsigned int i{0}; i < k; ++i ) {
        while ( true ) {
            bool found{false};
            unsigned int m{std::rand() % n};

            for ( unsigned int j{0}; j < i; ++j ) {
                if ( array[j] == m ) {
                    found = true;
                    break;
                }
            }

            if ( !found ) {
                array[i] = m;
                break;
            }
        }
    }

    return array;
}

int main() {
    // How often we should run each sample
    unsigned int NUM_RUNS{100};
    time_t t_max{0};

    // Calculate the average run time for n = 1000, 2000, ..., 100000
    time_t t0{time( nullptr )};

    // Run this NUM_RUNS times
    for ( unsigned int i{0}; i < NUM_RUNS; ++i ) {
        time_t s0{time( nullptr )};
        delete[] choose( 1000000, 500000 );
        time_t s1{time( nullptr ) - s0};

        if ( s1 > t_max ) {
            t_max = s1;
        }

        std::cout << s1 << std::endl;
    }

    time_t t1{time( nullptr ) - t0};

    std::cout << "Average: " << static_cast<double>( t1 )/NUM_RUNS << std::endl;
    std::cout << "Maximum: " << t_max << std::endl;

    return 0;
}