Then I think this is the same as the "naive algorithm" I described (perhaps inadequately) which, at each pass, moves to a growing sequence at the bottom of the deck, card #0, #1, #2, etc., (plus any unbroken sequence that follows a given card). Needing N passes in the worst case, to sort N cards.
Maybe the IBM 1130 card-sorting program was no cleverer than this (I never used it that much), but I have a strong feeling it's possible to do much better. On Tue, Aug 14, 2012 at 6:58 PM, Roger Hui <[email protected]> wrote: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
