I can't address how the "Music" app works — I have a 160MB iPod Classic and I, too, have had issues with how the iPhone now (and for some time) has handled music playback.
That said, I do have a solution to playing an entire playlist in its entirety without it repeating any songs. I've been doing this for over a decade now and I have some 10.4K songs in my library as of this writing. This system works using multiple devices. I use two different iPods (a classic and a second generation nano), iTunes itself, and, once upon a time, I used my iPhone (until I grew to dislike the interface to the degree that I do now).
Here's how I do it:
1) Create a smart playlist, and instruct it to contain only songs played before March 29, 2017 (the day should be whatever date you want to begin listening to your playlist, and needs to begin on a date after the completion of your last cycle, which, in this case, would need to be March 28, 2017).
2) Make sure that your iTunes preferences are configured to sync playback information across devices (whether through the store or through home sharing).
3) Make sure that the playlist is set to "live updating."
4) Name the playlist. By way of example, I'm going to call my hypothetical list "itunes list".
5) Duplicate the playlist (or build another). I'll name this next one "iphone list".
6) Determine how much drive space you want to (and can) devote to music storage on the device (i.e., the iPhone). I have 48.25GB free on my phone. Based on that, I'll open "iphone list", and I'll check the "limit" box, which should, by default, read "Limit to 0 items selected by random." [The number and two words in bold are the criteria you can choose for this sorting option.] I'm going to change "0" to "40", "items" to "GB", and I'm going to leave "random" alone.
7) Connect your iPhone to iTunes. Deselect all playlists and other music that you may currently by syncing to your phone. Select the "iphone list". Make sure that it has no option to play music other than the music on your playlist will be stored locally once you sync your phone.
8) Repeat if necessary. I have a list limited to 1.8GB for my iPod Nano (which I use when I run). My iPod Classic is large enough to hold my entire music library, so it uses the same list that iTunes uses.
If everything works properly (which I will not guarantee since I'm not familiar with the "music" app), whenever a song is played, it should be updated to reflect its last playdate and, at that point, "kicked off" of the list. When you sync your iPhone with iTunes, iTunes will update its library and it will remove those songs from the master playlist (and any other satellite playlists that you've set up will no longer be able to select those songs).
There may be times when the Music app crashes, and, in cases like those, it may not remember what songs were played and when (the same can happen on old school iPods, too). Your mileage may vary, but, in terms of best practices, start a playlist on your satellite device after a fresh sync to iTunes and use "pause" to start and stop the list. If you use "stop", or if you command it to "play" the entire list again, there is always the chance that the app may not have removed the songs that you've already played from the playlist. Even if you have not exhausted the playlist when you return to your computer, sync your iPhone to iTunes religiously. The songs that have not been played will remain on your device. The songs that have been played will disappear, and new songs, that have not yet been played during the cycle, will replace the ones that have been played.
I wish that this system worked as flawlessly as it did under iTunes 6, but it no longer does. Apple has done too many weird things to iTunes that can complicate playback—especially during the last two or three dozen songs. Still, that's the best system that I've found to date, and it should insure that the same group of songs aren't available for the Music app to choose.
I hope that a similar system might solve your problem even though it my reply doesn't directly address the algorithm issue, and, regardless, I do hope that you find some solution to your problem that is more elegant than not.
Happy listening.
