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
