Suppose you wanted to choose $k$ digits from $0$ to $n - 1$.

You could proceed as follows:

1. Keep track of those $k$ entries you have found in an array.
2. Iterating $k$ times:
1. Choose a random entry between $0$ and $n - 1$.
2. If it is already in our array, return to Step i;
3. otherwise, put this new entry into our array and continue.

Here is an implementation of this algorithm; however, you may also want to try this yourself, first.

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

Now, how long will this algorithm run? One significant issue is we can never be sure that it will even finish; after all, there is a non-zero probability that any sequence of $N$ randomly chosen values between $0$ and $n - 1$ are not already in our array of found values.

Now, one way of testing this algorithm would be to try to time how long it takes to run choose( n, n ) for different values of $n$; however, without much thought; however, if $k > \frac{n}{2}$, it would be easy to find choose( n, n - k ). Thus, the program average.cpp calculates choose( n, n/2 ) for $n = 1000, 2000, 3000, \ldots, 100000$.

Now, it may happen that in calling choose( 1000, 500 ) that all $500$ selections are indeed unique, so instead of calling choose( 1000, 500 ) just once and timing it, we will instead call choose( 1000, 500 ) one hundred times, and then print the average run time. This gives the following times:

$n$	Average run time of choose( n, n/2 ) (${\rm s}$)
1000	0.00
2000	0.00
3000	0.00
4000	0.00
5000	0.00
6000	0.01
7000	0.00
8000	0.00
9000	0.01
10000	0.01
11000	0.01
12000	0.01
13000	0.02
14000	0.01
15000	0.02
16000	0.02
17000	0.03
18000	0.02
19000	0.03
20000	0.03
21000	0.04
22000	0.04
23000	0.04
24000	0.05
25000	0.05
26000	0.06
27000	0.06
28000	0.06
29000	0.07
30000	0.08
31000	0.07
32000	0.09
33000	0.09
34000	0.09
35000	0.10
36000	0.11
37000	0.11
38000	0.12
39000	0.13
40000	0.13
41000	0.13
42000	0.15
43000	0.15
44000	0.16
45000	0.17
46000	0.17
47000	0.18
48000	0.19
49000	0.20
50000	0.20
51000	0.21
52000	0.23
53000	0.23
54000	0.23
55000	0.25
56000	0.26
57000	0.27
58000	0.27
59000	0.29
60000	0.29
61000	0.31
62000	0.31
63000	0.33
64000	0.33
65000	0.35
66000	0.35
67000	0.37
68000	0.38
69000	0.39
70000	0.40
71000	0.42
72000	0.42
73000	0.44
74000	0.44
75000	0.46
76000	0.48
77000	0.48
78000	0.50
79000	0.51
80000	0.53
81000	0.53
82000	0.55
83000	0.57
84000	0.57
85000	0.60
86000	0.60
87000	0.62
88000	0.63
89000	0.65
90000	0.66
91000	0.68
92000	0.69
93000	0.71
94000	0.72
95000	0.74
96000	0.76
97000	0.77
98000	0.78
99000	0.81
100000	0.81

Looking at this data, it may be difficult to see the trend; however, an image makes the trend clear:

Figure 1. The run-time of choose( n, n/2 ) for $n = 1000, 2000, ..., 100000$.

The red line in Figure 1 is the best-fitting least-squares quadratic polynomial $p(n) = 2.8195 \times 10^{-8} n + 8.1437\times 10^{-11} n^2$.

What this trend suggests is that if you were to try to calculate choose( 1000000, 500000 ), it would take on average 81.5 seconds!

The program maximum.cpp executes choose( 1000000, 500000 ) a total of 100 times, and on average each execution is 82.07 seconds, and and the worst-case run time was 84 seconds.

A different approach

Instead, consider the following algorithm:

1. Create an array of capacity $n$, and initialize the entries from $0$ to $n - 1$.
2. Now, for $i = 0, \ldots, k - 1$, do the following:
1. Select a random entry from $i$ to $n - i$ and swap that entry with the entry $i$.

The $k$ entries chosen from $0$ to $n - 1$ now occupy the entries $0$ through $k - 1$ in the given array.

Implement this new function.

Trade-offs

This new function is faster than the one that we implemented above: it always finishes executing in $k$ steps after initializing an array of capacity $n$.

Notice, however, that while this function will run much faster when finding choose( 100000, 50000 ), it may actually be slower when calculating choose( 100000, 5 ). Additionally, while in many cases it may be faster, the size of the array is $n$, while the size of the array for the function implemented above is only $k$.