evenly distributing duplicates throughout a randomized list (playlist shuffle)

user_2802450 0
Viewed 87

I need to shuffle about 1,000 strings of the form "title - artist", where a number of the titles repeat (say "Silent Night"), and a number of the artists repeat (say, "Bing Crosby"). None of the "title - artist" combos repeat, and there are no additional hyphens.

I'd like to end up with a list with as much space as possible between identical titles and between identical artists.

I'm leaning toward just randomly shuffling the whole list many thousands of times, and keeping whichever one has the greatest distance between the closest pair of identical repeats.

Another brute force: shuffle (just once) then repeat tons of times: find the closest pair and swap one of them into a different random spot.

One seem better than the other? Anything a little smarter, but still easy?

Thanks a ton!

playlist shuffle random
1 Answers

Perfect John Coleman! Thank you! Identical question, with suggestions, here: https://softwareengineering.stackexchange.com/q/194480/233981

------------ EDIT ------------

I couldn't be happier with my result!

Contrary to the op (me) I ignored repeated artists. Two "Bing Crosby"s in a row really doesn't matter compared with two "White Christmas"s.

I took the most popular song and spread it evenly across an unpopulated array. Then the second most popular song and did the same, incrementing past any collisions with #1. Repeat through the entire list, including songs with 0 repeats filling in the last empty slots.

So every 34th track is (a different) "Silent Night" (#1), which is impossible to detect as a listener. Every 46th track is "White Christmas" (#2, starting at a different location, with collisions bumped to 1 past "Silent Night")....

For the listener it couldn't be more random, and has zero of the gotcha/repeats I always get with rand(), noise(), and all of their sisters. ;)

Something like this:

populate the result list with null's
for each unique title, sorted from greatest # of repeats -> fewest # of repeats {
    perfectSpacing = list.size() div (number of times this title repeats)
    i = random(list.size())  // random starting location for this title
    for each unique version of this title {
        while (list[i] != null) // bump past populated slots, wrapping around
            i = (i + 1) % list.size()
        list[i] = current version of the current title
        i = (i + perfectSpacing) % list.size()
        // jump the ideal distance for the next version of this title
    }
}

Although "bumping past collisions" introduces the risk of wrapping around and creating a back-to-back repeat, the number of repeats in the data set are too few to allow it. Almost half of them don't repeat at all, and for those that do repeat, the curve from "lots of repeats" to "only a few repeats" degrades very rapidly.

Hope that help somebody some day!

user_28024500
Related