"Playlist" shuffle

I'm surprised I've never seen this mentioned anywhere, so I'm leaving it here.

Consider the standard Fisher-Yates algorithm:
1
2
3
4
5
6
7
8
9
10
template <typename It>
void random_shuffle(It begin, It end, Rng &rng){
    size_t n = end - begin;
    for (size_t i = 0; i < n; i++){
        size_t j = rng(i, n);
        assert(i <= j && j < n);
        if (i != j)
            std::swap(begin[i], begin[j]);
    }
}

Let's generalize it a bit:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Shuffle the range [begin; out_end) using the range
//[begin; out_end)+[out_end; in_end). At the end, [begin; out_end) is shuffled
//and [out_end; in_end) is less-than-shuffled.
template <typename It>
void random_shuffle2(It begin, It in_end, It out_end, Rng &rng){
    assert(out_end <= in_end);
    size_t n = out_end - begin;
    size_t m = in_end - begin;
    for (size_t i = 0; i < n; i++){
        size_t j = rng(i, m);
        assert(i <= j && j < m);
        if (i != j)
            std::swap(begin[i], begin[j]);
    }
}

void random_shuffle(It begin, It end, Rng &rng){
    random_shuffle2(begin, end, end, rng);
}

Now we can define
1
2
3
4
5
6
7
8
template <typename It>
void playlist_random_shuffle(It begin, It end, Rng &rng){
    auto n = end - begin;
    auto n1 = begin + n / 3;
    auto n2 = begin + n * 2 / 3;
    random_shuffle2(begin, n2, n1, rng);
    random_shuffle(n1, end, rng);
}

What's the point? If you randomize a playlist by reshuffling it each time it reaches the end, this method prevents the same tracks from being too close to one another between successive loops. In other words, playlist_random_shuffle([1, 2, 3]) will never return [3, 1, 2].
I don't understand what you are trying to achieve. The algorithm shuffles the first third into the first two-thirds, then the last two-thirds into itself. So it can never shuffle something from the last third into the first third. I don't get it. For example, given [1,2,3] it can return [1,2,3].
I don't understand what you are trying to achieve.
As stated, the goal is to prevent the same item from being too close to itself in successive loops. More formally, none of the elements in the last third of the unshuffled sequence appear in the first third of the shuffled sequence.

The algorithm shuffles the first third into the first two-thirds
Other way around.

For example, given [1,2,3] it can return [1,2,3].
It's pretty useless example, because Fisher-Yates does this too.
As stated, the goal is to prevent the same item from being too close to itself in successive loops

No. You said "prevents the same tracks from being too close to one another between successive loops", which is not the same (or even intelligible).

Other way around.

Disagree. Depends on how you interpret it, I guess.

It's pretty useless example, because Fisher-Yates does this too.

I don't care what a normal shuffle does. The point is that surely [1,2,3] is "close to" [1,2,3].

Anyway, whatever, sorry for showing any interest. Won't happen again.
Last edited on
You said "prevents the same tracks from being too close to one another between successive loops", which is not the same (or even intelligible).
One is a more general rephrasing of the other. What's not the same are "x is unintelligible" and "I don't understand x"; which is fine, but let's call things what they are.

Suppose you have a deck of cards and you pull one from the top, look at it, then place it in a separate deck. When you're left without cards you take the second deck, reshuffle it, and start over. If you shuffle it with Fisher-Yates, nothing prevents the first card you pull after shuffling from being the same as the last card you pulled before shuffling. This is fine if you aim for uniformity in a mathematical sense, but not if you aim for "variety" in an intuitive human sense.

I don't care what a normal shuffle does.
You can't understand what it does if you don't understand how it differs from Fisher-Yates. How it differs is that for any given input, the possible outputs are fewer than those of Fisher-Yates (which are all possible permutations). Thus you should not look at which outputs it may return, but at which outputs it won't return.

Anyway, whatever, sorry for showing any interest.
I don't know if you realize this, but your manner of writing is rather aggressive. I've many times seen you get into arguments with people who felt (IMO justifiably) insulted by how you talked to them. I don't think there's anything necessarily wrong with that, but I do think it's a bit silly to get offended when the other person replies in kind.
helios,
I know this isn't related to the topic, but I just wanted to see what kind of reactions I'll get.

There's something interesting that I've noticed in the short time I've been on this site:

It appears that there are two main kinds of people who post here, and their differences emerge when they encounter someone who gives a wrong answer, or who disagrees with them.

The first kind consists of people who usually say something to the effect of "You don't know what you're talking about," or "That's wrong."

The second kind, in the same situation, say "No, that's wrong," or "I always thought..." and proceed to explain.

Now, I'm not saying either of those is bad, although you can probably tell which kind I prefer. I just wanted to send a message to the first kind of people:

Don't just say "You're wrong" and let it go at that. Nobody learns anything that way, except that the solution that was proposed is wrong. Rather, tell them exactly what is wrong with their answer, and tell them how to correct it, or give them an example of a correct answer.

"Correct" and "Incorrect" being: an answer that works for the OP, and one that doesn't, respectively.

Just wanted to throw that out there.

max
The type of response you get get would tend to be related to how you give the incorrect answer to someone and how often. The 'slap down' type of response tends to be aimed at the type of person that give bad answers in a authoritative manner or very consistently.

Just an observation from an old timer.
Mmm, that is a very good point. I guess I didn't think about that. Thank you for pointing it out, I think from now on I should try to be more careful in how I phrase stuff, especially since I am not an expert by anyone's standards (except perhaps my brother's ;)
"Correct" and "Incorrect" being: an answer that works for the OP, and one that doesn't, respectively.
That's rather myopic. If you asked "I can't get my boot off. What's the best kind of tool to saw my foot off?", would the correct answer be "a circular saw" or "don't saw your foot off!"?
We get a lot of those types of question, where someone asks something weird because they've gone down some rabbit hole while trying to solve a reasonable problem and missed something obvious.

Suppose you see a post where I'm explaining what type of blade more easily cuts through bone, and you want to warn the OP not to listen to me but (for whatever reason) don't have the time to articulate what's wrong about my answer. Is it better to just leave my post there unchallenged or to just say "you're wrong" so OP knows to look at what I said more critically?
helios,
Another very good point; I should probably just delete my first post since I am realizing that it is really kind of silly griping about people "not being as polite as they could be," when I really don't know anything about it.

Edit:
Also just realized, I can't delete my post. Eh well. Live and learn, my grampa always said.
Last edited on
Topic archived. No new replies allowed.