"If you were able to pickup every store in town, randomly shuffle them, and place them into a nice straight line down one side of a road, then any old shuffling algorithm would work to get you a "random path" through the stores."
Isn't this always the case in software? Any set of entities represented in software can be hashed into a "straight line", in other words, you can assign a unique integer id to each one. And this works with your example of the street addresses of stores too -- just hash to a 32-bit value and sort them.
Certainly, if you can only see the paper in the box in front of you, the Sattolo solution makes sense. And it doesn't use any additional memory apart from one pointer per item (one piece of paper per store, in situ). There must be a more compelling application, though.
Incidentally, it's possible to use a maximal LFSR to generate a permutation (with only one cycle) without using extra storage and without using a shuffle. For cycling through very large numbers of elements this can be a great shortcut, if it's OK for the permutation to be the same each time. (Maybe could also use s-boxes to get a family of permutations)
You would probably enjoy checking out http://pcg-random.org/ it's got all that (tldr: powerful PRNG using very clever combination of simple permutation families), and a bunch of other useful properties. Also, no glossing over what exactly it does not (provably) do. It's not claiming to be cryptographically secure, for instance.
Isn't this always the case in software? Any set of entities represented in software can be hashed into a "straight line", in other words, you can assign a unique integer id to each one. And this works with your example of the street addresses of stores too -- just hash to a 32-bit value and sort them.
Certainly, if you can only see the paper in the box in front of you, the Sattolo solution makes sense. And it doesn't use any additional memory apart from one pointer per item (one piece of paper per store, in situ). There must be a more compelling application, though.
Incidentally, it's possible to use a maximal LFSR to generate a permutation (with only one cycle) without using extra storage and without using a shuffle. For cycling through very large numbers of elements this can be a great shortcut, if it's OK for the permutation to be the same each time. (Maybe could also use s-boxes to get a family of permutations)