Very nice, Marshall. That's just the sort of solution I was feeling towards.
Where I was going wrong was to look for a permutation solution to splitting the deck at each pass. It didn't occur to me to use number theory. For anybody on this list who might have difficulty following Marshall's code (...perish the thought!)... Verb: step -splits the stack and catenates the two piles. For a deck d of 10 cards, (x step d) must be called in turn with left args: 1, 2, 4, 8. It's revealing to replace (sort) with the following explicit definition... xsort=: 3 : 0 smoutput 0 __, y for_i. 1 2 4 8 do. smoutput i , __ , (y=. i step y) end. ) d=: 9 4 6 2 0 5 3 8 1 7 xsort d 0 __ 9 4 6 2 0 5 3 8 1 7 1 __ 4 6 2 0 8 9 5 3 1 7 2 __ 4 0 8 9 5 1 6 2 3 7 4 __ 0 8 9 1 2 3 4 5 6 7 8 __ 0 1 2 3 4 5 6 7 8 9 Reading from the top down, this shows the 4 passes of the IBM 1442 sufficient to sort the cards. Reading from the bottom up, this shows the 4 "riffles" (or alternatively, cuts) you must do ... http://en.wikipedia.org/wiki/Shuffle#Riffle to generate a given permutation: d . I think there's the outline of a proof here that a riffle shuffle can reach any permutation of N cards in log2(N) cuts. I agree in principle with Raul -- a first pass is necessary to read the numbered cards into the computer in the first place, so notionally you must add 1 to any total of passes. But I wasn't thinking of this as forming part of the actual algorithm. On Tue, Aug 14, 2012 at 7:57 PM, Marshall Lochbaum <[email protected]> wrote: > A base 2 radix sort should work here. That is: > On the first pass, place all the even cards in bin 0 and the odds in bin 1. > On the second pass, place all the cards congruent to 0 or 1 mod 4 in bin 0, > and the rest in bin 1. > Continue until the stack is sorted (2^.N passes). > > In J this is > step =. [: ; ] (</.~ {~ ~.@]) 2&|@:(<.@%~) > sort =: [: step&:>/ (<,~[:(<"0)2^[:i.@-@>.2^.#) > > Marshall > > On Tue, Aug 14, 2012 at 2:35 PM, Ian Clark <[email protected]> wrote: > >> 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 >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
