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

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

        // Run this NUM_RUNS times
        for ( unsigned int i{0}; i < NUM_RUNS; ++i ) {
            delete[] choose( n, n/2 );
        }

        time_t t1{time( nullptr ) - t0};

        std::cout << n << '\t' << static_cast<double>( t1 )/NUM_RUNS << std::endl;
    }

    return 0;
}