Page 1 of 1

Reverse Faro To Order Packet

Posted: April 8th, 2017, 11:40 am
by Bob Farmer
Imagine five cards in order, A, B, C, D

The cards are randomly mixed, then using a sorting procedure, the packet goes back into A, B, C, D order.

Let's say we assign a binary number to each of the cards:

A 00
B 01
C 10
D 11

Is there some sort of binary sorting procedure that could be used to return a random mix of the four cards to ABCD order?

This wouldn't be a real Reverse Faro where every second card is upjogged and then pulled out, it would be one where you run through the cards upjogging those required for the formula, pull them out, drop them on top then repeat until the cards are in ABCD order.

Re: Reverse Faro To Order Packet

Posted: April 8th, 2017, 12:13 pm
by Jonathan Townsend
You can implement classic computer science sorting algorithms using playing cards. Say a binary sort via the Hofzinser cull move - first step everything more or less then the middle value gets set into half packs. Second step done with each half pack moving everything above below .... for packets of more than ten cards it can get tedious.

Re: Reverse Faro To Order Packet

Posted: April 8th, 2017, 1:28 pm
by Michael Close
Brother John Hamman had a sequence for ordering a shuffled deck. Check out the various versions of the Chinese Miracle/Shuffle in the big Hamman book. You might be able to adapt that method.

Re: Reverse Faro To Order Packet

Posted: April 8th, 2017, 2:04 pm
by Dave Le Fevre
With only four cards, a simple logical sequence would be as follows. Assume that the desired order of the face-down packet is ABCD, and that you have the cards spread face up in your hands. You therefore wish to end up with ABCD from left to right.

while order is not ABCD
Upjog A
if B is to the right of A
then
Upjog B
if C is to the right of B
then
Upjog C
Strip out the upjogged card(s) and move them to the left
end

This is annoying. I've inserted leading spaces in the lines so that the algorithm makes sense. However, the forum software has removed them. As it's displayed, it doesn't make logical sense, and is wrong. Any idea how to insert leading spaces in a post?

Dave

Re: Reverse Faro To Order Packet

Posted: April 8th, 2017, 2:38 pm
by Richard Kaufman
What is a "leading space"?

Re: Reverse Faro To Order Packet

Posted: April 8th, 2017, 4:02 pm
by Dave Le Fevre
Space characters at the beginning of a line of text, in order to indent it

Re: Reverse Faro To Order Packet

Posted: April 8th, 2017, 5:25 pm
by Bob Farmer
Dave:

That's exactly what I'm looking ofr.

Would you have a version that sorts 12 cards into 1 to 12 order? The cards are astrological signs.

You can email me directly trickmail@cogeco.ca if the Forum isn't up to it.

What is this process called?

Re: Reverse Faro To Order Packet

Posted: April 9th, 2017, 12:07 am
by Bill Mullins
Bob Farmer wrote:Imagine five cards in order, A, B, C, D

For non-Canadians, five cards would be A, B, C, D, and E. I think mixing English and French confuses things.


For 4 cards A, B, C, D, randomly mixed, and assuming that you are holding them as a packet in your hands --

1st. Upjog B and D, strip them out, and move them as a group to the back of the packet. Don't disturb the relative order of A and C, or of B and D.
2nd. Upjog C and D, strip them out, and move them to the back of the packet
3rd. Packet should now be in A, B, C, D order

For 12 cards A - L

1st. Upjog B,D,F,H,J,L, strip them out, move them to the back
2nd. Upjog C,D,G,H,K,L, strip them out, move them to the back
3rd. Upjog E,F,G,H, strip them out, move them to the back
4th. Upjog I,J,K,L, strip them out, move them to the back
Packet should now be in A-L order.

General procedure for N cards
First, figure out what the smallest power of 2 is that is still greater than the number of cards involved. For 12 cards, that is 16 (= 2 to the 5th power). Your sorting process will take 1 fewer sorts than that. (sorting 12 cards took 4 sorts: 5 minus 1=4).

Second, Enumerate your cards in binary, starting with 0. For twelve cards, they numbered:

A 0 0000
B 1 0001
C 2 0010
D 3 0011
E 4 0100
F 5 0101
G 6 0110
H 7 0111
I 8 1000
J 9 1001
K 10 1010
L 11 1011

Third, sort as follows.
1st sort: upjog, strip, and move to the back every card which has a 1 in the 1's place of the binary number
2nd sort: upjog, strip, and move to the back every card which has a 1 in the 2's place of the binary number
3rd sort: upjog, strip and move to the back every card which has a 1 in the 4's place of the binary number
4th sort: upjog, strip and move to the back every card which has a 1 in the 8's place of the binary number.

If you had between 17 and 32 cards, it would take 5 sorts. If you had between 33 and 64 cards, it would take 6 sorts.
This process is called a binary radix sort. It is essentially what goes on in Bro John Hamman's Chinese Shuffle. Note that if you can remember your stack numbers in binary, that means that you could sort a deck that is in any arbitrary order into any given stack (Aronson, Tamariz, Nicola, etc) by passing through it only six times.

Nick Pudar has taken Marlo's idea of marking a deck with its stack number and Bob's Farmax marking system, and marks a deck in binary. This means that you can sort a deck from shuffled order into stack order by looking at the backs only, and you don't even have to memorize the binary numbers.

Re: Reverse Faro To Order Packet

Posted: April 9th, 2017, 12:24 am
by Bill Mullins
Above, where I said "smallest power of 2 is that is still greater than the number of cards", I should have said "smallest power of 2 is that is still greater or equal to than the number of cards". Sorting 16 cards takes 4 sorts.

Re: Reverse Faro To Order Packet

Posted: April 9th, 2017, 3:07 am
by Dave Le Fevre
Bob Farmer wrote:What is this process called?

It's a sorting algorithm.

My approach was a simple one, since there were only four cards. (Yes, I'd noticed the four-five discrepancy, but had decided not to mention it.)

For more cards, other algorithms are no doubt far more efficient, so I suggest that you go with Bill's suggestion.

Dave

Re: Reverse Faro To Order Packet

Posted: April 9th, 2017, 8:36 am
by Bob Farmer
Bill:

This is great--can hardly wait to try it out.

See:

http://www.timl.id.au/?p=23

Phase 1: Dealing

Deal the first card from the deck face up on the table. This is the first pile.
Take the next card from the deck. If it is smaller than the card in the first pile, place it on top of the first pile. If it’s larger than the card in the first pile, create a second pile to the right of the first pile.
Deal each subsequent card, placing it on the pile which has the smallest top card which is larger than the card being dealt. If the top card of all piles is smaller than the card being dealt, create a new pile to the right of the other piles.
Phase 2: Collecting

Pick up the smallest card. It will be on top of the left-most pile.
Pick up the next smallest card, it will be on top of one of the piles.
Continue picking up cards in order. The next card will always be on top of one of the piles.
Play a game of cards!

Re: Reverse Faro To Order Packet

Posted: April 9th, 2017, 3:39 pm
by Bill Mullins
As comments in the blog you linked to indicate, Tim has reinvented "Patience Sorting". And (surprise, surprise), Persi Diaconis has been there before him:
https://pdfs.semanticscholar.org/6578/2c451aadb336125462027d99349035c28b80.pdf

Re: Reverse Faro To Order Packet

Posted: April 9th, 2017, 5:14 pm
by Bill Mullins
If you find four sorts to be too many for 12 cards, you can (by doing base-3 math) reduce it to 3 sorts, at the expense of slightly more complicated mental gymnastics and card manipulation. Instead of holding a packet and upjogging some to separate them into two groups, you upjog and downjog to make three groups.

For 12 cards:

Card, Card #, trinary value

a 0 000
b 1 001
c 2 002
d 3 010
e 4 011
f 5 012
g 6 020
h 7 021
i 8 022
j 9 100
k 10 101
l 11 102

Go through the deck and downjog every card which has a 0 in the 1's place, and upjog every card which has a 2 in the 1's place. Strip out the downjogged cards, and place them at the front of the packet. Strip out the upjogged cards and place them at the back of the packet. Repeat for the 3's place, and the 9's place.

Specifically:
1st pass through: Downjog A, D, G, J. Upjog C, F, I, L. Strip out downjogs, move them to front, strip out upjogs, move them to back.
2nd pass: Downjog A, B, C, J, K, L . Upjog G, H, I. Strip out downjogs, move them to front, strip out upjogs, move them to back.
3rd pass: Downjog A - I and move to front (practically speaking, it is easier to upjog J, K, L and put them in the back).

The packet should be in order.

Re: Reverse Faro To Order Packet

Posted: April 9th, 2017, 9:01 pm
by Bob Farmer
Bill's solutions are just what I needed. Thank you Bill, will email you some interesting variations that don't use a strip-out.