The answer to question 2b is 12 17 2 7 13 18 3 8 14 19 4 9 15 20 5 10 16 1 6 11. For 2c, the answers are 3 out riffles, 6 in riffles and 8 breaks.#!/usr/bin/perl use strict; use warnings; use Test::More 'no_plan'; use integer; sub b {@_[1 .. @_ - 1, 0]} sub o { @_[map({$_, $_ + @_ / 2 + @_ % 2} 0 .. @_ / 2 - 1), @_ % 2 ? @_ / +2 : ()] } sub i { @_[map({$_ + @_ / 2, $_} 0 .. @_ / 2 - 1), @_ % 2 ? @_ + 1 : ()] } my $bal; $bal = qr /\( [^()]* (?: (??{$bal}) [^()]* )* \)/x; sub shuffle { my ($str, @deck) = @_; 1 while $str =~ s/([0-9]+)(?:([bio])|($bal))/($2 || $3) x $1/eg; $str =~ s/[^bio]+//g; foreach my $c (split //, $str) { no strict 'refs'; @deck = &$c(@deck) } @deck; } my @deck = 1 .. 8; is_deeply([shuffle ("i2o", @deck)], [5, 6, 7, 8, 1, 2, 3, 4 +]); is_deeply([shuffle ("3(b2(oi))", @deck)], [1, 6, 3, 2, 4, 5, 7, 8 +]); is_deeply([shuffle ("b", @deck)], [2, 3, 4, 5, 6, 7, 8, 1 +]); is_deeply([shuffle ("i", @deck)], [5, 1, 6, 2, 7, 3, 8, 4 +]); is_deeply([shuffle ("o", @deck)], [1, 5, 2, 6, 3, 7, 4, 8 +]); is_deeply([shuffle ("bioib", @deck)], [6, 1, 8, 3, 2, 5, 4, 7 +]); is_deeply([shuffle ("3i", @deck)], [8, 7, 6, 5, 4, 3, 2, 1 +]); is_deeply([shuffle ("2io", @deck)], [7, 8, 5, 6, 3, 4, 1, 2 +]); is_deeply([shuffle ("8b", @deck)], [1, 2, 3, 4, 5, 6, 7, 8 +]); is_deeply([shuffle ("b3oi", @deck)], [6, 2, 7, 3, 8, 4, 1, 5 +]); is_deeply([shuffle ("2(io)", @deck)], [6, 2, 5, 1, 8, 4, 7, 3 +]); is_deeply([shuffle ("b2(ib)o", @deck)], [2, 3, 1, 6, 7, 8, 5, 4 +]); is_deeply([shuffle ("3(i2(io)o)", @deck)], [3, 4, 1, 2, 7, 8, 5, 6 +]); is_deeply([shuffle ("4(4(io)2b)", @deck)], [5, 4, 3, 6, 8, 1, 2, 7 +]); is_deeply([shuffle ("5(6(bi)7(io))", @deck)], [1, 2, 8, 4, 5, 3, 7, 6 +]); is_deeply([shuffle ("2(3(4(io)b)b)b", @deck)], [1, 6, 4, 3, 5, 2, 8, 7 +]); __END__ ok 1 ok 2 ok 3 ok 4 ok 5 ok 6 ok 7 ok 8 ok 9 ok 10 ok 11 ok 12 ok 13 ok 14 ok 15 ok 16 1..16
The answer to 2d is "yes". It can be easily seen by constructing a graph with a nod for each possible permutation of the deck. Make a directed edge from node v to node w, if an in riffle shuffles the permutation associated with v to the permutation associated with w. Edges having the same begin and end point are fine. If repeatedly performing an in shuffle would not lead to the being situation, the graph will be without loops. But a directed graph without loops must contains sinks (nodes with incoming edges, and no outgoing edges). But a sink would mean a permutation that can't be shuffled. However, any permutation can be shuffled. Ergo, the graph must contain loops, and repeatedly shuffling will cause the begin permutation to reappear. This is true for any repeated shuffle based on a fixed permutation.
In reply to Re: Shuffling cards
by Anonymous Monk
in thread Shuffling cards
by amnesty_puppy
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |