I assumed as much, and the algorithm I described would work for the problem. If blank can be a character, then instead of j=9,8,7,...,0 you'd have j=9,8,7,...,0,' '.
On Tue, Aug 14, 2012 at 10:05 AM, Ian Clark <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
