Perhaps it was misleading of me to mention card columns 73-80. This was just a field into which an integer 0-99999999 could be put, to number the cards in their correct sequence. I was assuming (as was the convention for a program or data deck of N cards) they were numbered 1 to N. So it's just a problem of sorting numbered cards.
On Tue, Aug 14, 2012 at 4:53 PM, Roger Hui <[email protected]> wrote: > There is a linear algorithm that takes 80*n passes, based on lexicographic > sorting. > > for k=80,79,..,73, > keep a separate stack of collected cards, initially empty > for j=9,8,7,...,0 > output cards having value j in column k into hopper 2; the other cards > into hopper 1 > put the cards from hopper 2 on top of the separate stack of collected > cards; > put cards from hopper 1 into the input hopper for the next j > put the separate stack of collected cards into the input hopper for the > next k > > I think there's a "sorting card reader" with multiple (at least 10?) output > hoppers that can do this more efficient, taking n passes for sorting n > columns. > > > > On Tue, Aug 14, 2012 at 8:24 AM, Ian Clark <[email protected]> wrote: > >> 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 >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
