Puzzle... The IBM 1442 Card Reader http://en.wikipedia.org/wiki/IBM_1442 had two output hoppers. A deck of punched cards was generally numbered in cols 73-80. There was a program to sort a shuffled deck in several passes. Each pass would allocate cards to one or other hopper. The contents of hopper 2 were then piled on top of hopper 1 and the whole pile reloaded for another pass. When all the cards emerged in hopper 1, the stack was sorted.
How did that program work? A naive algorithm for the first pass is to output cards to hopper 2 until you hit card #0, sending it to hopper 1. If you subsequently hit card #1, send that to hopper 1 as well, and so on. That might be good enough to sort out the typical mishap of dropping the deck on the floor, which would leave longish sequences of cards in-order. But there's got to be a more efficient algorithm than that. The 1442 sorting process is the inverse of the so-called riffle-shuffle of playing cards, which appears empirically to be pretty effective at randomizing cards in as few as 3 or 4 cuts. If you know how to specify a "minimal-pass" riffle-shuffle to generate any given permutation, then you've solved the problem. Then what's the expected number of cuts you'd need to generate a given permutation which is a random choice of all (equi-likely) permutations? I'd conjecture (2^.N) for a deck of N cards. Unlike other questions I've posted, I don't have an immediate use for the answer to this one. It's just been bugging me. I'm supposed to know something about permutations, but I can't seem to make any progress. Trying to visualize it evokes the "butterfly" of the Cooley-Tukey FFT algorithm, but that may be only a chimera. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
