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:
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...