You must track the permutation you're stepping through.

E.g. you have 4 items. You shuffle them to get a random permutation:

4 2 1 3

Note: these are not indices, but identifiers. Let's say you go through the first two items:

4 2 <you're here> 1 3

And two new items arrive. You insert each item into a random position among the remaining items. E.g:

4 2 <you're here> 5 1 6 3

If items are to be deleted, there are two cases: either they have already been visited, in which case there's nothing to do, or they're in the remaining list, in which case you have to delete them from there.

I'm really enjoying the discussion on how shuffle means different things to different people (I personally prefer random, but implementing `shuffle` specifically sounds fun with all of this)

> You insert each item into a random position among the remaining items

Thinking about shuffle + adding, I would have thought "even if it's added to a past position", e.g.

`5 4 6 21 3` as valid.

What do folks expect out of shuffle when it reaches the end? A new shuffle, or repeat with the same permutation?

I think all of this depends on the UI presentation, but when “shuffle” is used, I think a good starting point is “what would a person expect from a deck of cards”, since that’s where the metaphor started.

I don’t think that provides a totally clear answer to “what happens at the end”, but for me it’d lean me towards “a new shuffle”, because for me most of the time a shuffled deck of cards draws its last card, the deck will be shuffled again before drawing new cards.