10
\$\begingroup\$

Challenge

In the shortest amount of code:

  1. Compute the length of the permutation cycle of a perfect shuffle on a deck of cards of any size n (where n ≥ 2 and n is even).
  2. Output a table of all cycle lengths for 2 ≤ n ≤ 1000 (n even).

Note that there are two basic ways of defining a perfect shuffle. There is the out-shuffle, which keeps the first card on top and the last card on bottom, and there is the in-shuffle, which moves the first and last cards one position toward the center. You may choose whether you are doing an out-shuffle or an in-shuffle; the algorithm is almost identical between the two.

  • out-shuffle of 10-card deck: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5,10].
  • in-shuffle of 10-card deck: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10,5].

Graphical example

Here, we see that an out-shuffle on a 20-card deck has a cycle length of 18 steps. (This is for illustration only; your solution is not required to output cycles graphically.) The classic 52-card deck, on the other hand, has an out-shuffle cycle length of only 8 steps (not shown).

Out-shuffle cycle for 20-card deck

An in-shuffle on a 20-card deck has a cycle length of only 6 steps.

In-shuffle cycle for 20-card deck

Tabular example of output

Your program should output something similar to this, although you may choose any tabular format that you like best. This is for an out-shuffle:

2 1
4 2
6 4
8 3
10 6
12 10
14 12
16 4
18 8
20 18
22 6
24 11
26 20
28 18
30 28
32 5
34 10
36 12
38 36
40 12
...many lines omitted...
1000 36

Questions

  1. Does there seem to be any connection between the number input n and its cycle count, when n is a power of 2?
  2. How about when n is not a power of 2?
  3. Curiously, a 1000-card deck has an out-shuffle cycle count of only 36, while a 500-card deck has an out-shuffle cycle count of 166. Why might this be?
  4. What is the largest number you can find whose cycle count c is vastly smaller than n, meaning that ratio n/c is maximized?
\$\endgroup\$
  • 1
    \$\begingroup\$ Very closely related. \$\endgroup\$ – Martin Ender Aug 6 '15 at 21:24
  • \$\begingroup\$ Ya, that's more about displaying the results, though. This question is about generating a table for any value of n; it's more mathematical in nature. \$\endgroup\$ – Todd Lehman Aug 6 '15 at 21:31
  • \$\begingroup\$ confused me there with the 6/8 cycles in the demonstrated for a good while :) (i thought my imlementation was wrong). finally i looked at the image and saw it is a 6 cycle, so i edited it. funny \$\endgroup\$ – proud haskeller Aug 6 '15 at 22:27
  • \$\begingroup\$ @proud haskeller — ah yes, thank you! \$\endgroup\$ – Todd Lehman Aug 6 '15 at 22:33
  • 1
    \$\begingroup\$ This is sequence A002326. \$\endgroup\$ – orlp Aug 7 '15 at 10:28
6
\$\begingroup\$

Haskell, 47 46 44 (in shuffle)

[[i|i<-[1..],mod(2^i)n<2]!!0|n<-[3,5..1001]]

the basic realization is that this is the order of 2 in the multiplicative group of modulus n+1.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can remove the l= - the expression itself is enough. That's a valid program when run on the interactive command line. \$\endgroup\$ – orlp Aug 7 '15 at 10:47
5
\$\begingroup\$

Pyth, 16 bytes

mfq1%^2T+3yd)500

In-shuffle using A002326.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 22 bytes

V500,JyhNl{.u.iFc2NJUJ

Try it online: Demonstration. Replace 500 with a smaller number, if it is too slow.

Explanation:

V500                     for N in [0, 1, ..., 499]:
      yhN                   (N + 1) * 2
     J                      assign to J
           .u      JUJ      apply the following expression J times
                            to N, starting with N = [0, 1, ..., J - 1],
                            and return all intermediate results:
                c2N            split N into 2 halfs
             .iF               and interleave them
         l{                 remove duplicates and give length
    ,                       make a pair and print
\$\endgroup\$
  • 1
    \$\begingroup\$ It's kind of crazy that a pyth solution which does the actual work of shuffling and counting the decks is only half as long as the haskell solution which uses an easy formula the instantly predict the result \$\endgroup\$ – Falco Aug 7 '15 at 8:27
  • \$\begingroup\$ @Falco I know right \$\endgroup\$ – proud haskeller Aug 7 '15 at 14:05
  • 1
    \$\begingroup\$ @Falco I actually tried to do a pyth portof my answer but I couldn't figure how to do it. So I just ended up playing with pyth for half an hour \$\endgroup\$ – proud haskeller Aug 7 '15 at 17:30
  • \$\begingroup\$ Be glad you didn't try <>< \$\endgroup\$ – Falco Aug 7 '15 at 18:50
2
\$\begingroup\$

Mathematica, 53 (in-shuffle)

Grid[{2#,MultiplicativeOrder[2,2#+1]}&/@Range[1,500]]

or, not antagonistically spaced

Grid[{2 #, MultiplicativeOrder[2, 2 # + 1]} & /@ Range[1, 501]]

Output:

   2    2
   4    4
   6    3
   8    6
  10   10
  12   12
  14    4
  16    8
  18   18
  20    6
 (* digits, digits, bo bidgits, banana fana, ... *)
  498  166
  500  166
 (* skip a bit, brother ...  *)
  998   36
 1000   60

Every entry in both columns is horizontally centered in their columns, but I don't have the fractional spaces &#8194; ... &#8202; here to replicate that.

Observations:

  • Out-shuffle is in-shuffle on a deck two cards smaller. (Note that the first and last cards are in fixed position throughout the out-shuffle demonstration.) Consequently, the two choices will lead to similar output lists -- the second column will be shifted by one row. Regarding the "powers of two" hint, the in-shuffle of power of two decks has the pattern {2^n - 2, n}, {2^n, 2n}. (Out-shuffle pairs 2^n with n.)
  • Observe in the in-shuffle example that the distance of 2 from the closest end of the deck doubles at each step. {2, 4, 8, 15 = -5, -10, -20}. In fact, this is true for every card. We therefore only need to know which power of 2 is congruent to 1 mod n+1 where n is the number of cards. (Note that in the example, the cards in the last column, column -1, are doubled to the penultimate column, -2, meaning that 0 is congruent to one more card than is in the deck, thus "mod n+1".) Therefore, the MultiplicativeOrder[] function is the way to go (in Mathematica).
  • By default, one would try TableForm[] instead of Grid[], but the output is similar.
\$\endgroup\$
  • \$\begingroup\$ Your example output seems wrong \$\endgroup\$ – proud haskeller Aug 7 '15 at 11:50
  • \$\begingroup\$ @proudhaskeller : for in-shuffle or out-shuffle? Either is permitted. (And as noted, the one is just a one row shift in the right column of the other.) \$\endgroup\$ – Eric Towers Aug 7 '15 at 16:26
  • \$\begingroup\$ They both don't seem to fit. Look up the example output in the question. Maybe your example output is wrong and the actual code is right and the example is just outdated, I don't know, but it doesn't seem to fit. \$\endgroup\$ – proud haskeller Aug 7 '15 at 17:04
  • \$\begingroup\$ proudhaskeller : I seem to have typoed my example output at "8". And muddled in- and out- at least once. Editing. Thanks for being persistent. :-) \$\endgroup\$ – Eric Towers Aug 10 '15 at 17:11
0
\$\begingroup\$

C,86 (or 84)

Score excludes unnecessary whitespace, included for clarity.

i,j,n;
main(){
  for(;n<1002;printf("%d %d\n",n,j),n+=2)
    for(i=n,j=1;i=i*2%(n+1),i-n;)j++;
}

This is an in-shuffle, which as pointed out by others, is just the out shuffle with the stationary cards at both ends removed.

As pointed out by others, in the in-shuffle, the position of each card doubles each time, but this must be taken modulo n+1. I like to think of the extra card position being position zero to the left of the table (you can think of this as holding both the stationary cards from the out-shuffle too). Obviously the position of the card must always be positive, hence the zero position always remains empty for the in-shuffle case.

The code initialises i to the value of n. Then it multiplies by 2, takes the result mod (n+1) and checks to see if i has returned to its initial value (i-n is zero.) It increments j for each iteration, except the last one (hence the need initialise j to 1.)

In principle, i could be with any value in the range 1..n, so long as the comparison at the end checked if it was intialised to the same number. The reason for picking n was to make sure the program works for the case n==0. the problem was that any number modulo (0+1) is zero, so the loop never terminated in this case if i was initialised to a constant such as 1.

The question examples includes the equivalent case n==2 for the out shuffle, so it was interpreted that this case is required. If it isn't, two bytes n, could be saved by initializing i to 1, the same value as j.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.