Relffhus is a playlist for Noatun (noatun.kde.org) that better handles random play order. It behaves very similarly to the default "Split" playlist of Noatun, but uses weighting factors for each song in the list to make sure that the most recently played songs are the least likely to be played next. Relffuhs guarantees that no song will be played twice in a row.

To be of any use, Relffuhs needs Noatun, as well as the dev libs of Noatun, and KDE, and QT, etc., to compile.

You can download it at the project page.

Here's a screenie: