Imagine you have a bunch of stores in your city. Each store has a piece of paper in a box that has the name and address of that store. You want to shuffle the pieces of paper in the the stores in such a way that if you start at any random store, read the piece of paper there, go to the listed store, then read that store's paper, and continue likewise, you'll reach all stores.
Shuffling like this isn't as as easy as it seems. If you give a store a paper with its own address, then a visitor to that store will be stuck there forever.
Of course it's easy to check for not giving the same address to a store when shuffling, but what about checking for store A points to B points to C points back to A? Oops. Anyone who reaches these stores will never go on to the rest of the stores.
Sattolo's shuffle handles this elegantly.
Caring about the number of cycles only matters if the values of your array are actually indexs back into your array.
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.
(One huge practical difference with Sattolo's is that no element ends up in its original place after the shuffle.
This can be good, or very bad, depending on what you are using it for.)
"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.
Shuffling like this isn't as as easy as it seems. If you give a store a paper with its own address, then a visitor to that store will be stuck there forever.
Of course it's easy to check for not giving the same address to a store when shuffling, but what about checking for store A points to B points to C points back to A? Oops. Anyone who reaches these stores will never go on to the rest of the stores.
Sattolo's shuffle handles this elegantly.
Caring about the number of cycles only matters if the values of your array are actually indexs back into your array.
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.
(One huge practical difference with Sattolo's is that no element ends up in its original place after the shuffle.
This can be good, or very bad, depending on what you are using it for.)