Suppose you want to implement an algorithm that plays a play-list in such a way that each song is only played once. From the previous problem of choosing $k$ items from $n$, one approach would be to create an array of $n$ entries, and to then select one at random, swapping it to the back.

Once all $n$ songs have been played, it is only necessary to continue using the same array, even if all the entries have now been randomly permuted:

#include <cstdlib>
#include <utility>
#include <iostream>
unsigned int next_song( unsigned int *array, unsigned int n, unsigned int k );

unsigned int next_song( unsigned int *array, unsigned int n, unsigned int k ) {
    unsigned int i{k % n};

    if ( i == (n - 1) ) {
        return array[0];
    } else {
        unsigned int next{std::rand() % (n - i)};

        std::swap( array[next], array[n - i - 1] );

        return array[n - i - 1];
    }
}

int main() {
    unsigned int const CAPACITY{17};
    unsigned int song_list[CAPACITY];

    for ( unsigned int i{0}; i < CAPACITY; ++i ) {
        song_list[i] = i;
    }

    for ( unsigned int i{0}; i < 10*CAPACITY; ++i ) {
        std::cout << next_song( song_list, CAPACITY, i ) << ' ';

        if ( (i % CAPACITY) == CAPACITY - 1 ) {
            std::cout << std::endl;
        }
    }
}

The output of this program is:

10 6 12 5 1 7 0 2 15 13 9 14 16 3 8 4 11 
7 8 13 6 12 15 14 2 10 5 0 4 1 3 16 11 9 
14 16 13 2 7 1 8 12 0 4 5 10 15 11 6 9 3 
8 6 0 7 3 13 4 11 10 16 9 5 2 1 14 12 15 
14 11 12 13 7 5 15 3 4 0 1 9 2 10 6 8 16 
11 4 1 16 8 13 6 7 14 0 9 5 3 12 2 10 15 
8 6 7 0 10 4 14 13 1 11 15 2 5 9 16 12 3 
1 8 4 0 12 2 6 13 5 10 9 11 16 15 3 7 14 
8 1 12 6 14 13 0 11 16 15 5 3 10 9 2 7 4 
11 9 4 0 7 13 2 8 5 1 10 14 3 15 16 6 12 

This ensures that within any cycle of 17 songs, there is no repetition; however, note that between the end of the second-last cycle and the start of the last cycle, Songs 4, 7 and 9 would be played twice within nine songs; between the end of the first and start of the second cycle, Song 8 is played twice within five songs;

and, at the end of the fourth and start of the fifth cycle, Song 12 is also played twice within five songs.

Can you think of an algorithm that, for examples:

1. Ensures that within any cycle of $n$ songs, each song is played exactly once, and
3. A song is never played more than once every $n/2$ songs.

Hint: Consider a sliding window of size n/2.

Another weakness of our function above is that it does require an array of capacity $n$. If our primary goal was to play each song at most once per cycle, one solution is to use number theory:

TO BE COMPLETED...