Perfect shuffle: Difference between revisions
m (→{{header|REXX}}: optimized the program slightly.) |
m (→{{header|Wren}}: Minor tidy) |
||
(151 intermediate revisions by 68 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
A perfect shuffle (or [https://en.wikipedia.org/wiki/Faro_shuffle faro/weave shuffle]) means splitting a deck of cards into equal halves, and perfectly interleaving them - so that you end up with the first card from the left half, followed by the first card from the right half, and so on: |
|||
<big> |
|||
A deck can be divided in two halves: |
|||
<!-- START OF DIAGRAM --> |
|||
::: <div style="display:inline-block;margin:0.5em 1.5em"><tt><span style="background:#8DF">7♠</span> <span style="background:#8DF">8♠</span> <span style="background:#8DF">9♠</span> <span style="background:#FB5">J♠</span> <span style="background:#FB5">Q♠</span> <span style="background:#FB5">K♠</span></tt></div><div style="display:inline-block">→<div style="display:inline-block;vertical-align:middle;margin:0.5em 1.5em"><tt><span style="background:#8DF">7♠</span> <span style="background:#8DF">8♠</span> <span style="background:#8DF">9♠</span></tt><br><tt> <span style="background:#FB5">J♠</span> <span style="background:#FB5">Q♠</span> <span style="background:#FB5">K♠</span></tt></div></div><div style="display:inline-block">→<div style="display:inline-block;vertical-align:middle;margin:0.5em 1.5em"><tt><span style="background:#8DF">7♠</span> <span style="background:#FB5">J♠</span> <span style="background:#8DF">8♠</span> <span style="background:#FB5">Q♠</span> <span style="background:#8DF">9♠</span> <span style="background:#Fb5">K♠</span></tt></div></div> |
|||
<!-- END OF DIAGRAM --> |
|||
</big> |
|||
When you repeatedly perform perfect shuffles on an even-sized deck of unique cards, it will at some point arrive back at its original order. How many shuffles this takes, depends solely on the number of cards in the deck - for example for a deck of eight cards it takes three shuffles: |
|||
a b c d e f -> a b c | d e f |
|||
<big> |
|||
Perfect shuffling means taking one card from the first half, one card for the second half, and so on: |
|||
<!-- START OF DIAGRAM --> |
|||
::::: {| style="border-spacing:0.5em 0;border-collapse:separate;margin:0 1em;text-align:right" |
|||
|- |
|||
| <small>''original:''</small> || |
|||
<tt style="background:#122CF8;color:#B8C0FD;padding:0 0.3em">1</tt> |
|||
<tt style="background:#332AD7;color:#C2C0F3;padding:0 0.3em">2</tt> |
|||
<tt style="background:#5428B7;color:#CCBFEA;padding:0 0.3em">3</tt> |
|||
<tt style="background:#752696;color:#D6BEE0;padding:0 0.3em">4</tt> |
|||
<tt style="background:#962576;color:#E0BED6;padding:0 0.3em">5</tt> |
|||
<tt style="background:#B72355;color:#EABDCC;padding:0 0.3em">6</tt> |
|||
<tt style="background:#D82135;color:#F3BDC3;padding:0 0.3em">7</tt> |
|||
<tt style="background:#F92015;color:#FDBDB9;padding:0 0.3em">8</tt> |
|||
|- |
|||
| <small>''after 1st shuffle:''</small> || |
|||
<tt style="background:#122CF8;color:#B8C0FD;padding:0 0.3em">1</tt> |
|||
<tt style="background:#962576;color:#E0BED6;padding:0 0.3em">5</tt> |
|||
<tt style="background:#332AD7;color:#C2C0F3;padding:0 0.3em">2</tt> |
|||
<tt style="background:#B72355;color:#EABDCC;padding:0 0.3em">6</tt> |
|||
<tt style="background:#5428B7;color:#CCBFEA;padding:0 0.3em">3</tt> |
|||
<tt style="background:#D82135;color:#F3BDC3;padding:0 0.3em">7</tt> |
|||
<tt style="background:#752696;color:#D6BEE0;padding:0 0.3em">4</tt> |
|||
<tt style="background:#F92015;color:#FDBDB9;padding:0 0.3em">8</tt> |
|||
|- |
|||
| <small>''after 2nd shuffle:''</small> || |
|||
<tt style="background:#122CF8;color:#B8C0FD;padding:0 0.3em">1</tt> |
|||
<tt style="background:#5428B7;color:#CCBFEA;padding:0 0.3em">3</tt> |
|||
<tt style="background:#962576;color:#E0BED6;padding:0 0.3em">5</tt> |
|||
<tt style="background:#D82135;color:#F3BDC3;padding:0 0.3em">7</tt> |
|||
<tt style="background:#332AD7;color:#C2C0F3;padding:0 0.3em">2</tt> |
|||
<tt style="background:#752696;color:#D6BEE0;padding:0 0.3em">4</tt> |
|||
<tt style="background:#B72355;color:#EABDCC;padding:0 0.3em">6</tt> |
|||
<tt style="background:#F92015;color:#FDBDB9;padding:0 0.3em">8</tt> |
|||
|- |
|||
| <small>''after 3rd shuffle:''</small> || |
|||
<tt style="background:#122CF8;color:#B8C0FD;padding:0 0.3em">1</tt> |
|||
<tt style="background:#332AD7;color:#C2C0F3;padding:0 0.3em">2</tt> |
|||
<tt style="background:#5428B7;color:#CCBFEA;padding:0 0.3em">3</tt> |
|||
<tt style="background:#752696;color:#D6BEE0;padding:0 0.3em">4</tt> |
|||
<tt style="background:#962576;color:#E0BED6;padding:0 0.3em">5</tt> |
|||
<tt style="background:#B72355;color:#EABDCC;padding:0 0.3em">6</tt> |
|||
<tt style="background:#D82135;color:#F3BDC3;padding:0 0.3em">7</tt> |
|||
<tt style="background:#F92015;color:#FDBDB9;padding:0 0.3em">8</tt> |
|||
|} |
|||
<!-- END OF DIAGRAM --> |
|||
</big> |
|||
<p style="font-size:115%; margin:1em 0 0.5em 0">'''''The Task'''''</p> |
|||
a d b e c f |
|||
# Write a function that can perform a perfect shuffle on an even-sized list of values. |
|||
# Call this function repeatedly to count how many shuffles are needed to get a deck back to its original order, for each of the deck sizes listed under "Test Cases" below. |
|||
#* <small>You can use a list of numbers (or anything else that's convenient) to represent a deck; just make sure that all "cards" are unique within each deck.</small> |
|||
#* <small>Print out the resulting shuffle counts, to demonstrate that your program passes the test-cases.</small> |
|||
<p style="font-size:115%; margin:1em 0 0.5em 0">'''''Test Cases'''''</p> |
|||
A remarkable feature of perfect shuffling is that the deck goes back to the start after a number that is fixed for every n (where n is the number of cards) |
|||
::::: {| class="wikitable" |
|||
* Implement a magic shuffle function |
|||
|- |
|||
* Print the number of perfect shuffles needed to go back to start for decks from 2 to 10,000 cards (by steps of 2), determined by using the magic shuffle function |
|||
! input ''(deck size)'' !! output ''(number of shuffles required)'' |
|||
|- |
|||
| 8 || 3 |
|||
|- |
|||
| 24 || 11 |
|||
|- |
|||
| 52 || 8 |
|||
|- |
|||
| 100 || 30 |
|||
|- |
|||
| 1020 || 1018 |
|||
|- |
|||
| 1024 || 10 |
|||
|- |
|||
| 10000 || 300 |
|||
|} |
|||
<br><br> |
|||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="11l">F flatten(lst) |
|||
[Int] r |
|||
L(sublst) lst |
|||
L(i) sublst |
|||
r [+]= i |
|||
R r |
|||
F magic_shuffle(deck) |
|||
V half = deck.len I/ 2 |
|||
R flatten(zip(deck[0 .< half], deck[half ..])) |
|||
F after_how_many_is_equal(start, end) |
|||
V deck = magic_shuffle(start) |
|||
V counter = 1 |
|||
L deck != end |
|||
deck = magic_shuffle(deck) |
|||
counter++ |
|||
R counter |
|||
print(‘Length of the deck of cards | Perfect shuffles needed to obtain the same deck back’) |
|||
L(length) (8, 24, 52, 100, 1020, 1024, 10000) |
|||
V deck = Array(0 .< length) |
|||
V shuffles_needed = after_how_many_is_equal(deck, deck) |
|||
print(‘#<5 | #.’.format(length, shuffles_needed))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Length of the deck of cards | Perfect shuffles needed to obtain the same deck back |
|||
8 | 3 |
|||
24 | 11 |
|||
52 | 8 |
|||
100 | 30 |
|||
1020 | 1018 |
|||
1024 | 10 |
|||
10000 | 300 |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU. |
|||
<syntaxhighlight lang="action!">DEFINE MAXDECK="5000" |
|||
PROC Order(INT ARRAY deck INT count) |
|||
INT i |
|||
FOR i=0 TO count-1 |
|||
DO |
|||
deck(i)=i |
|||
OD |
|||
RETURN |
|||
BYTE FUNC IsOrdered(INT ARRAY deck INT count) |
|||
INT i |
|||
FOR i=0 TO count-1 |
|||
DO |
|||
IF deck(i)#i THEN |
|||
RETURN (0) |
|||
FI |
|||
OD |
|||
RETURN (1) |
|||
PROC Shuffle(INT ARRAY src,dst INT count) |
|||
INT i,i1,i2 |
|||
i=0 i1=0 i2=count RSH 1 |
|||
WHILE i<count |
|||
DO |
|||
dst(i)=src(i1) i==+1 i1==+1 |
|||
dst(i)=src(i2) i==+1 i2==+1 |
|||
OD |
|||
RETURN |
|||
PROC Test(INT ARRAY deck,deck2 INT count) |
|||
INT ARRAY tmp |
|||
INT n |
|||
Order(deck,count) |
|||
n=0 |
|||
DO |
|||
Shuffle(deck,deck2,count) |
|||
tmp=deck deck=deck2 deck2=tmp |
|||
n==+1 |
|||
Poke(77,0) ;turn off the attract mode |
|||
PrintF("%I cards -> %I iterations%E",count,n) |
|||
Put(28) ;move cursor up |
|||
UNTIL IsOrdered(deck,count) |
|||
OD |
|||
PutE() |
|||
RETURN |
|||
PROC Main() |
|||
INT ARRAY deck(MAXDECK),deck2(MAXDECK) |
|||
INT ARRAY counts=[8 24 52 100 1020 1024 MAXDECK] |
|||
INT i |
|||
FOR i=0 TO 6 |
|||
DO |
|||
Test(deck,deck2,counts(i)) |
|||
OD |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Perfect_shuffle.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
8 cards -> 3 iterations |
|||
24 cards -> 11 iterations |
|||
52 cards -> 8 iterations |
|||
100 cards -> 30 iterations |
|||
1020 cards -> 1018 iterations |
|||
1024 cards -> 10 iterations |
|||
5000 cards -> 357 iterations |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
<syntaxhighlight lang="ada">with ada.text_io;use ada.text_io; |
|||
procedure perfect_shuffle is |
|||
function count_shuffle (half_size : Positive) return Positive is |
|||
subtype index is Natural range 0..2 * half_size - 1; |
|||
subtype index_that_move is index range index'first+1..index'last-1; |
|||
type deck is array (index) of index; |
|||
initial, d, next : deck; |
|||
count : Natural := 1; |
|||
begin |
|||
for i in index loop initial (i) := i; end loop; |
|||
d := initial; |
|||
loop |
|||
for i in index_that_move loop |
|||
next (i) := (if d (i) mod 2 = 0 then d(i)/2 else d(i)/2 + half_size); |
|||
end loop; |
|||
exit when next (index_that_move)= initial(index_that_move); |
|||
d := next; |
|||
count := count + 1; |
|||
end loop; |
|||
return count; |
|||
end count_shuffle; |
|||
test : array (Positive range <>) of Positive := (8, 24, 52, 100, 1020, 1024, 10_000); |
|||
begin |
|||
for size of test loop |
|||
put_line ("For" & size'img & " cards, there are "& count_shuffle (size / 2)'img & " shuffles needed."); |
|||
end loop; |
|||
end perfect_shuffle;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
For 8 cards, there are 3 shuffles needed. |
|||
For 24 cards, there are 11 shuffles needed. |
|||
For 52 cards, there are 8 shuffles needed. |
|||
For 100 cards, there are 30 shuffles needed. |
|||
For 1020 cards, there are 1018 shuffles needed. |
|||
For 1024 cards, there are 10 shuffles needed. |
|||
For 10000 cards, there are 300 shuffles needed. |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
<syntaxhighlight lang="algol68"># returns an array of the specified length, initialised to an ascending sequence of integers # |
|||
OP DECK = ( INT length )[]INT: |
|||
BEGIN |
|||
[ 1 : length ]INT result; |
|||
FOR i TO UPB result DO result[ i ] := i OD; |
|||
result |
|||
END # DECK # ; |
|||
# in-place shuffles the deck as per the task requirements # |
|||
# LWB deck is assumed to be 1 # |
|||
PROC shuffle = ( REF[]INT deck )VOID: |
|||
BEGIN |
|||
[ 1 : UPB deck ]INT result; |
|||
INT left pos := 1; |
|||
INT right pos := ( UPB deck OVER 2 ) + 1; |
|||
FOR i FROM 2 BY 2 TO UPB result DO |
|||
result[ left pos ] := deck[ i - 1 ]; |
|||
result[ right pos ] := deck[ i ]; |
|||
left pos +:= 1; |
|||
right pos +:= 1 |
|||
OD; |
|||
FOR i TO UPB deck DO deck[ i ] := result[ i ] OD |
|||
END # SHUFFLE # ; |
|||
# compares two integer arrays for equality # |
|||
OP = = ( []INT a, b )BOOL: |
|||
IF LWB a /= LWB b OR UPB a /= UPB b |
|||
THEN # the arrays have different bounds # |
|||
FALSE |
|||
ELSE |
|||
BOOL result := TRUE; |
|||
FOR i FROM LWB a TO UPB a WHILE result := a[ i ] = b[ i ] DO SKIP OD; |
|||
result |
|||
FI # = # ; |
|||
# compares two integer arrays for inequality # |
|||
OP /= = ( []INT a, b )BOOL: NOT ( a = b ); |
|||
# returns the number of shuffles required to return a deck of the specified length # |
|||
# back to its original state # |
|||
PROC count shuffles = ( INT length )INT: |
|||
BEGIN |
|||
[] INT original deck = DECK length; |
|||
[ 1 : length ]INT shuffled deck := original deck; |
|||
INT count := 1; |
|||
WHILE shuffle( shuffled deck ); |
|||
shuffled deck /= original deck |
|||
DO |
|||
count +:= 1 |
|||
OD; |
|||
count |
|||
END # count shuffles # ; |
|||
# test the shuffling # |
|||
[]INT lengths = ( 8, 24, 52, 100, 1020, 1024, 10 000 ); |
|||
FOR l FROM LWB lengths TO UPB lengths DO |
|||
print( ( whole( lengths[ l ], -8 ) + ": " + whole( count shuffles( lengths[ l ] ), -6 ), newline ) ) |
|||
OD</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8: 3 |
|||
24: 11 |
|||
52: 8 |
|||
100: 30 |
|||
1020: 1018 |
|||
1024: 10 |
|||
10000: 300 |
|||
</pre> |
|||
=={{header|APL}}== |
|||
{{works with|Dyalog APL}} |
|||
<syntaxhighlight lang="apl">faro ← ∊∘⍉(2,2÷⍨≢)⍴⊢ |
|||
count ← {⍺←⍵ ⋄ ⍺≡r←⍺⍺ ⍵:1 ⋄ 1+⍺∇r} |
|||
(⊢,[1.5] (faro count ⍳)¨) 8 24 52 100 1020 1024 10000</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300</pre> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">perfectShuffle: function [deckSize][ |
|||
deck: 1..deckSize |
|||
original: new deck |
|||
halfDeck: deckSize/2 |
|||
i: 1 |
|||
while [true][ |
|||
deck: flatten couple first.n: halfDeck deck last.n: halfDeck deck |
|||
if deck = original -> return i |
|||
i: i+1 |
|||
] |
|||
] |
|||
loop [8 24 52 100 1020 1024 10000] 's -> |
|||
print [ |
|||
pad.right join @["Perfect shuffles required for deck size " to :string s ":"] 48 |
|||
perfectShuffle s |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Perfect shuffles required for deck size 8: 3 |
|||
Perfect shuffles required for deck size 24: 11 |
|||
Perfect shuffles required for deck size 52: 8 |
|||
Perfect shuffles required for deck size 100: 30 |
|||
Perfect shuffles required for deck size 1020: 1018 |
|||
Perfect shuffles required for deck size 1024: 10 |
|||
Perfect shuffles required for deck size 10000: 300</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight lang="autohotkey">Shuffle(cards){ |
|||
n := cards.MaxIndex()/2, res := [] |
|||
loop % n |
|||
res.push(cards[A_Index]), res.push(cards[round(A_Index + n)]) |
|||
return res |
|||
}</syntaxhighlight> |
|||
Examples:<syntaxhighlight lang="autohotkey">test := [8, 24, 52, 100, 1020, 1024, 10000] |
|||
for each, val in test |
|||
{ |
|||
cards := [], original:=rep:="" |
|||
loop, % val |
|||
cards.push(A_Index), original .= (original?", ":"") A_Index |
|||
while (res <> original) |
|||
{ |
|||
res := "" |
|||
for k, v in (cards := Shuffle(cards)) |
|||
res .= (res?", ":"") v |
|||
rep := A_Index |
|||
} |
|||
result .= val "`t" rep "`n" |
|||
} |
|||
MsgBox % result |
|||
return</syntaxhighlight> |
|||
Outputs:<pre>8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300</pre> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c">/* ===> INCLUDES <============================================================*/ |
|||
#include <stdlib.h> |
|||
#include <stdio.h> |
|||
#include <string.h> |
|||
/* ===> CONSTANTS <===========================================================*/ |
|||
#define N_DECKS 7 |
|||
const int kDecks[N_DECKS] = { 8, 24, 52, 100, 1020, 1024, 10000 }; |
|||
/* ===> FUNCTION PROTOTYPES <=================================================*/ |
|||
int CreateDeck( int **deck, int nCards ); |
|||
void InitDeck( int *deck, int nCards ); |
|||
int DuplicateDeck( int **dest, const int *orig, int nCards ); |
|||
int InitedDeck( int *deck, int nCards ); |
|||
int ShuffleDeck( int *deck, int nCards ); |
|||
void FreeDeck( int **deck ); |
|||
/* ===> FUNCTION DEFINITIONS <================================================*/ |
|||
int main() { |
|||
int i, nCards, nShuffles; |
|||
int *deck = NULL; |
|||
for( i=0; i<N_DECKS; ++i ) { |
|||
nCards = kDecks[i]; |
|||
if( !CreateDeck(&deck,nCards) ) { |
|||
fprintf( stderr, "Error: malloc() failed!\n" ); |
|||
return 1; |
|||
} |
|||
InitDeck( deck, nCards ); |
|||
nShuffles = 0; |
|||
do { |
|||
ShuffleDeck( deck, nCards ); |
|||
++nShuffles; |
|||
} while( !InitedDeck(deck,nCards) ); |
|||
printf( "Cards count: %d, shuffles required: %d.\n", nCards, nShuffles ); |
|||
FreeDeck( &deck ); |
|||
} |
|||
return 0; |
|||
} |
|||
int CreateDeck( int **deck, int nCards ) { |
|||
int *tmp = NULL; |
|||
if( deck != NULL ) |
|||
tmp = malloc( nCards*sizeof(*tmp) ); |
|||
return tmp!=NULL ? (*deck=tmp)!=NULL : 0; /* (?success) (:failure) */ |
|||
} |
|||
void InitDeck( int *deck, int nCards ) { |
|||
if( deck != NULL ) { |
|||
int i; |
|||
for( i=0; i<nCards; ++i ) |
|||
deck[i] = i; |
|||
} |
|||
} |
|||
int DuplicateDeck( int **dest, const int *orig, int nCards ) { |
|||
if( orig != NULL && CreateDeck(dest,nCards) ) { |
|||
memcpy( *dest, orig, nCards*sizeof(*orig) ); |
|||
return 1; /* success */ |
|||
} |
|||
else { |
|||
return 0; /* failure */ |
|||
} |
|||
} |
|||
int InitedDeck( int *deck, int nCards ) { |
|||
int i; |
|||
for( i=0; i<nCards; ++i ) |
|||
if( deck[i] != i ) |
|||
return 0; /* not inited */ |
|||
return 1; /* inited */ |
|||
} |
|||
int ShuffleDeck( int *deck, int nCards ) { |
|||
int *copy = NULL; |
|||
if( DuplicateDeck(©,deck,nCards) ) { |
|||
int i, j; |
|||
for( i=j=0; i<nCards/2; ++i, j+=2 ) { |
|||
deck[j] = copy[i]; |
|||
deck[j+1] = copy[i+nCards/2]; |
|||
} |
|||
FreeDeck( © ); |
|||
return 1; /* success */ |
|||
} |
|||
else { |
|||
return 0; /* failure */ |
|||
} |
|||
} |
|||
void FreeDeck( int **deck ) { |
|||
if( *deck != NULL ) { |
|||
free( *deck ); |
|||
*deck = NULL; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Cards count: 8, shuffles required: 3. |
|||
Cards count: 24, shuffles required: 11. |
|||
Cards count: 52, shuffles required: 8. |
|||
Cards count: 100, shuffles required: 30. |
|||
Cards count: 1020, shuffles required: 1018. |
|||
Cards count: 1024, shuffles required: 10. |
|||
Cards count: 10000, shuffles required: 300. |
|||
Press "Enter" to quit... |
|||
</pre> |
|||
=={{header|C sharp}}== |
|||
{{works with|C sharp|6}} |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Collections.Generic; |
|||
using System.Linq; |
|||
public static class PerfectShuffle |
|||
{ |
|||
static void Main() |
|||
{ |
|||
foreach (int input in new [] {8, 24, 52, 100, 1020, 1024, 10000}) { |
|||
int[] numbers = Enumerable.Range(1, input).ToArray(); |
|||
Console.WriteLine($"{input} cards: {ShuffleThrough(numbers).Count()}"); |
|||
} |
|||
IEnumerable<T[]> ShuffleThrough<T>(T[] original) { |
|||
T[] copy = (T[])original.Clone(); |
|||
do { |
|||
yield return copy = Shuffle(copy); |
|||
} while (!Enumerable.SequenceEqual(original, copy)); |
|||
} |
|||
} |
|||
public static T[] Shuffle<T>(T[] array) { |
|||
if (array.Length % 2 != 0) throw new ArgumentException("Length must be even."); |
|||
int half = array.Length / 2; |
|||
T[] result = new T[array.Length]; |
|||
for (int t = 0, l = 0, r = half; l < half; t+=2, l++, r++) { |
|||
result[t] = array[l]; |
|||
result[t+1] = array[r]; |
|||
} |
|||
return result; |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8 cards: 3 |
|||
24 cards: 11 |
|||
52 cards: 8 |
|||
100 cards: 30 |
|||
1020 cards: 1018 |
|||
1024 cards: 10 |
|||
10000 cards: 300 |
|||
</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp"> |
|||
#include <iostream> |
|||
#include <algorithm> |
|||
#include <vector> |
|||
int pShuffle( int t ) { |
|||
std::vector<int> v, o, r; |
|||
for( int x = 0; x < t; x++ ) { |
|||
o.push_back( x + 1 ); |
|||
} |
|||
r = o; |
|||
int t2 = t / 2 - 1, c = 1; |
|||
while( true ) { |
|||
v = r; |
|||
r.clear(); |
|||
for( int x = t2; x > -1; x-- ) { |
|||
r.push_back( v[x + t2 + 1] ); |
|||
r.push_back( v[x] ); |
|||
} |
|||
std::reverse( r.begin(), r.end() ); |
|||
if( std::equal( o.begin(), o.end(), r.begin() ) ) return c; |
|||
c++; |
|||
} |
|||
} |
|||
int main() { |
|||
int s[] = { 8, 24, 52, 100, 1020, 1024, 10000 }; |
|||
for( int x = 0; x < 7; x++ ) { |
|||
std::cout << "Cards count: " << s[x] << ", shuffles required: "; |
|||
std::cout << pShuffle( s[x] ) << ".\n"; |
|||
} |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Cards count: 8, shuffles required: 3. |
|||
Cards count: 24, shuffles required: 11. |
|||
Cards count: 52, shuffles required: 8. |
|||
Cards count: 100, shuffles required: 30. |
|||
Cards count: 1020, shuffles required: 1018. |
|||
Cards count: 1024, shuffles required: 10. |
|||
Cards count: 10000, shuffles required: 300. |
|||
</pre> |
|||
=={{header|Clojure}}== |
|||
<syntaxhighlight lang="clojure">(defn perfect-shuffle [deck] |
|||
(let [half (split-at (/ (count deck) 2) deck)] |
|||
(interleave (first half) (last half)))) |
|||
(defn solve [deck-size] |
|||
(let [original (range deck-size) |
|||
trials (drop 1 (iterate perfect-shuffle original)) |
|||
predicate #(= original %)] |
|||
(println (format "%5s: %s" deck-size |
|||
(inc (some identity (map-indexed (fn [i x] (when (predicate x) i)) trials))))))) |
|||
(map solve [8 24 52 100 1020 1024 10000])</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8: 3 |
|||
24: 11 |
|||
52: 8 |
|||
100: 30 |
|||
1020: 1018 |
|||
1024: 10 |
|||
10000: 300 |
|||
</pre> |
|||
=={{header|Common Lisp}}== |
|||
<syntaxhighlight lang="lisp">(defun perfect-shuffle (deck) |
|||
(let* ((half (floor (length deck) 2)) |
|||
(left (subseq deck 0 half)) |
|||
(right (nthcdr half deck))) |
|||
(mapcan #'list left right))) |
|||
(defun solve (deck-size) |
|||
(loop with original = (loop for n from 1 to deck-size collect n) |
|||
for trials from 1 |
|||
for deck = original then shuffled |
|||
for shuffled = (perfect-shuffle deck) |
|||
until (equal shuffled original) |
|||
finally (format t "~5D: ~4D~%" deck-size trials))) |
|||
(solve 8) |
|||
(solve 24) |
|||
(solve 52) |
|||
(solve 100) |
|||
(solve 1020) |
|||
(solve 1024) |
|||
(solve 10000)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 8: 3 |
|||
24: 11 |
|||
52: 8 |
|||
100: 30 |
|||
1020: 1018 |
|||
1024: 10 |
|||
10000: 300</pre> |
|||
=={{header|D}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="d">import std.stdio; |
|||
void main() { |
|||
auto sizes = [8, 24, 52, 100, 1020, 1024, 10_000]; |
|||
foreach(s; sizes) { |
|||
writefln("%5s : %5s", s, perfectShuffle(s)); |
|||
} |
|||
} |
|||
int perfectShuffle(int size) { |
|||
import std.exception : enforce; |
|||
enforce(size%2==0); |
|||
import std.algorithm : copy, equal; |
|||
import std.range; |
|||
int[] orig = iota(0, size).array; |
|||
int[] process; |
|||
process.length = size; |
|||
copy(orig, process); |
|||
for(int count=1; true; count++) { |
|||
process = roundRobin(process[0..$/2], process[$/2..$]).array; |
|||
if (equal(orig, process)) { |
|||
return count; |
|||
} |
|||
} |
|||
assert(false, "How did this get here?"); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 8 : 3 |
|||
24 : 11 |
|||
52 : 8 |
|||
100 : 30 |
|||
1020 : 1018 |
|||
1024 : 10 |
|||
10000 : 300</pre> |
|||
=={{header|Delphi}}== |
|||
{{libheader| System.SysUtils}} |
|||
{{Trans|Go}} |
|||
<syntaxhighlight lang="delphi"> |
|||
program Perfect_shuffle; |
|||
{$APPTYPE CONSOLE} |
|||
uses |
|||
System.SysUtils; |
|||
type |
|||
TDeck = record |
|||
Cards: TArray<Integer>; |
|||
Len: Integer; |
|||
constructor Create(deckSize: Integer); overload; |
|||
constructor Create(deck: TDeck); overload; |
|||
procedure shuffleDeck(); |
|||
class operator Equal(a, b: TDeck): boolean; |
|||
function ShufflesRequired: Integer; |
|||
procedure Assign(a: TDeck); |
|||
end; |
|||
{ TDeck } |
|||
procedure TDeck.Assign(a: TDeck); |
|||
begin |
|||
Len := a.Len; |
|||
Cards := copy(a.Cards, 0, len); |
|||
end; |
|||
constructor TDeck.Create(deckSize: Integer); |
|||
begin |
|||
if deckSize < 1 then |
|||
raise Exception.Create('Error: Deck size must have above zero'); |
|||
if Odd(deckSize) then |
|||
raise Exception.Create('Error: Deck size must be even'); |
|||
SetLength(Cards, deckSize); |
|||
Len := deckSize; |
|||
for var i := 0 to High(Cards) do |
|||
Cards[i] := i; |
|||
end; |
|||
constructor TDeck.Create(deck: TDeck); |
|||
begin |
|||
Assign(deck); |
|||
end; |
|||
class operator TDeck.Equal(a, b: TDeck): boolean; |
|||
begin |
|||
if a.len <> b.len then |
|||
raise Exception.Create('Error: Decks aren''t equally sized'); |
|||
if a.Len = 0 then |
|||
exit(True); |
|||
for var i := 0 to a.Len - 1 do |
|||
if a.Cards[i] <> b.Cards[i] then |
|||
exit(False); |
|||
Result := True; |
|||
end; |
|||
procedure TDeck.shuffleDeck; |
|||
var |
|||
tmp: TArray<Integer>; |
|||
begin |
|||
SetLength(tmp, len); |
|||
for var i := 0 to len div 2 - 1 do |
|||
begin |
|||
tmp[i * 2] := Cards[i]; |
|||
tmp[i * 2 + 1] := Cards[len div 2 + i]; |
|||
end; |
|||
Cards := copy(tmp, 0, len); |
|||
end; |
|||
function TDeck.ShufflesRequired: Integer; |
|||
var |
|||
ref: TDeck; |
|||
begin |
|||
Result := 1; |
|||
ref := TDeck.Create(self); |
|||
shuffleDeck; |
|||
while not (self = ref) do |
|||
begin |
|||
shuffleDeck; |
|||
inc(Result); |
|||
end; |
|||
end; |
|||
const |
|||
cases: TArray<Integer> = [8, 24, 52, 100, 1020, 1024, 10000]; |
|||
begin |
|||
for var size in cases do |
|||
begin |
|||
var deck := TDeck.Create(size); |
|||
writeln(format('Cards count: %d, shuffles required: %d', [size, deck.ShufflesRequired])); |
|||
end; |
|||
readln; |
|||
end.</syntaxhighlight> |
|||
=={{header|Dyalect}}== |
|||
{{trans|C#}} |
|||
<syntaxhighlight lang="dyalect">func shuffle(arr) { |
|||
if arr.Length() % 2 != 0 { |
|||
throw @InvalidValue(arr.Length()) |
|||
} |
|||
var half = arr.Length() / 2 |
|||
var result = Array.Empty(arr.Length()) |
|||
var (t, l, r) = (0, 0, half) |
|||
while l < half { |
|||
result[t] = arr[l] |
|||
result[t+1] = arr[r] |
|||
l += 1 |
|||
r += 1 |
|||
t += 2 |
|||
} |
|||
result |
|||
} |
|||
func arrayEqual(xs, ys) { |
|||
if xs.Length() != ys.Length() { |
|||
return false |
|||
} |
|||
for i in xs.Indices() { |
|||
if xs[i] != ys[i] { |
|||
return false |
|||
} |
|||
} |
|||
return true |
|||
} |
|||
func shuffleThrough(original) { |
|||
var copy = original.Clone() |
|||
while true { |
|||
copy = shuffle(copy) |
|||
yield copy |
|||
if arrayEqual(original, copy) { |
|||
break |
|||
} |
|||
} |
|||
} |
|||
for input in yields { 8, 24, 52, 100, 1020, 1024, 10000} { |
|||
var numbers = [1..input] |
|||
print("\(input) cards: \(shuffleThrough(numbers).Length())") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>8 cards: 3 |
|||
24 cards: 11 |
|||
52 cards: 8 |
|||
100 cards: 30 |
|||
1020 cards: 1018 |
|||
1024 cards: 10 |
|||
10000 cards: 300</pre> |
|||
=={{header|EasyLang}}== |
|||
{{trans|Phix}} |
|||
<syntaxhighlight> |
|||
proc pshuffle . deck[] . |
|||
mp = len deck[] / 2 |
|||
in[] = deck[] |
|||
for i = 1 to mp |
|||
deck[2 * i - 1] = in[i] |
|||
deck[2 * i] = in[i + mp] |
|||
. |
|||
. |
|||
proc test size . . |
|||
for i to size |
|||
deck0[] &= i |
|||
. |
|||
deck[] = deck0[] |
|||
repeat |
|||
pshuffle deck[] |
|||
cnt += 1 |
|||
until deck[] = deck0[] |
|||
. |
|||
print cnt |
|||
. |
|||
for size in [ 8 24 52 100 1020 1024 10000 ] |
|||
test size |
|||
. |
|||
</syntaxhighlight> |
|||
=={{header|EchoLisp}}== |
|||
<syntaxhighlight lang="lisp"> |
|||
;; shuffler : a permutation vector which interleaves both halves of deck |
|||
(define (make-shuffler n) |
|||
(let ((s (make-vector n))) |
|||
(for ((i (in-range 0 n 2))) (vector-set! s i (/ i 2))) |
|||
(for ((i (in-range 0 n 2))) (vector-set! s (1+ i) (+ (/ n 2) (vector-ref s i)))) |
|||
s)) |
|||
;; output : (n . # of shuffles needed to go back) |
|||
(define (magic-shuffle n) |
|||
(when (odd? n) (error "magic-shuffle:odd input" n)) |
|||
(let [(deck (list->vector (iota n))) ;; (0 1 ... n-1) |
|||
(dock (list->vector (iota n))) ;; keep trace or init deck |
|||
(shuffler (make-shuffler n))] |
|||
(cons n (1+ |
|||
(for/sum ((i Infinity)) ; (in-naturals missing in EchoLisp v2.9) |
|||
(vector-permute! deck shuffler) ;; permutes in place |
|||
#:break (eqv? deck dock) ;; compare to first |
|||
1))))) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<syntaxhighlight lang="lisp"> |
|||
map magic-shuffle '(8 24 52 100 1020 1024 10000)) |
|||
→ ((8 . 3) (24 . 11) (52 . 8) (100 . 30) (1020 . 1018) (1024 . 10) (10000 . 300)) |
|||
;; Let's look in the On-line Encyclopedia of Integer Sequences |
|||
;; Given a list of numbers, the (oeis ...) function looks for a sequence |
|||
(lib 'web) |
|||
Lib: web.lib loaded. |
|||
map magic-shuffle (range 2 18 2)) |
|||
→ ((2 . 1) (4 . 2) (6 . 4) (8 . 3) (10 . 6) (12 . 10) (14 . 12) (16 . 4)) |
|||
(oeis '(1 2 4 3 6 10 12 4)) |
|||
→ Sequence A002326 found |
|||
</syntaxhighlight> |
|||
=={{header|Elixir}}== |
|||
{{trans|Ruby}} |
|||
<syntaxhighlight lang="elixir">defmodule Perfect do |
|||
def shuffle(n) do |
|||
start = Enum.to_list(1..n) |
|||
m = div(n, 2) |
|||
shuffle(start, magic_shuffle(start, m), m, 1) |
|||
end |
|||
defp shuffle(start, start, _, step), do: step |
|||
defp shuffle(start, deck, m, step) do |
|||
shuffle(start, magic_shuffle(deck, m), m, step+1) |
|||
end |
|||
defp magic_shuffle(deck, len) do |
|||
{left, right} = Enum.split(deck, len) |
|||
Enum.zip(left, right) |
|||
|> Enum.map(&Tuple.to_list/1) |
|||
|> List.flatten |
|||
end |
|||
end |
|||
Enum.each([8, 24, 52, 100, 1020, 1024, 10000], fn n -> |
|||
step = Perfect.shuffle(n) |
|||
IO.puts "#{n} : #{step}" |
|||
end)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8 : 3 |
|||
24 : 11 |
|||
52 : 8 |
|||
100 : 30 |
|||
1020 : 1018 |
|||
1024 : 10 |
|||
10000 : 300 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
let perfectShuffle xs = |
|||
let h = (List.length xs) / 2 |
|||
xs |
|||
|> List.mapi (fun i x->(if i<h then i * 2 else ((i-h) * 2) + 1), x) |
|||
|> List.sortBy fst |
|||
|> List.map snd |
|||
let orderCount n = |
|||
let xs = [1..n] |
|||
let rec spin count ys = |
|||
if xs=ys then count |
|||
else ys |> perfectShuffle |> spin (count + 1) |
|||
xs |> perfectShuffle |> spin 1 |
|||
[ 8; 24; 52; 100; 1020; 1024; 10000 ] |> List.iter (fun n->n |> orderCount |> printfn "%d %d" n) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300 |
|||
</pre> |
|||
=={{header|Factor}}== |
|||
<syntaxhighlight lang="factor">USING: arrays formatting kernel math prettyprint sequences |
|||
sequences.merged ; |
|||
IN: rosetta-code.perfect-shuffle |
|||
CONSTANT: test-cases { 8 24 52 100 1020 1024 10000 } |
|||
: shuffle ( seq -- seq' ) halves 2merge ; |
|||
: shuffle-count ( n -- m ) |
|||
<iota> >array 0 swap dup [ 2dup = ] [ shuffle [ 1 + ] 2dip ] |
|||
do until 2drop ; |
|||
"Deck size" "Number of shuffles required" "%-11s %-11s\n" printf |
|||
test-cases [ dup shuffle-count "%-11d %-11d\n" printf ] each</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Deck size Number of shuffles required |
|||
8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300 |
|||
</pre> |
|||
=={{header|Fortran}}== |
|||
<syntaxhighlight lang="fortran">MODULE PERFECT_SHUFFLE |
|||
IMPLICIT NONE |
|||
CONTAINS |
|||
! Shuffle the deck/array of integers |
|||
FUNCTION SHUFFLE(NUM_ARR) |
|||
INTEGER, DIMENSION(:), INTENT(IN) :: NUM_ARR |
|||
INTEGER, DIMENSION(SIZE(NUM_ARR)) :: SHUFFLE |
|||
INTEGER :: I, IDX |
|||
IF (MOD(SIZE(NUM_ARR), 2) .NE. 0) THEN |
|||
WRITE(*,*) "ERROR: SIZE OF DECK MUST BE EVEN NUMBER" |
|||
CALL EXIT(1) |
|||
END IF |
|||
IDX = 1 |
|||
DO I=1, SIZE(NUM_ARR)/2 |
|||
SHUFFLE(IDX) = NUM_ARR(I) |
|||
SHUFFLE(IDX+1) = NUM_ARR(SIZE(NUM_ARR)/2+I) |
|||
IDX = IDX + 2 |
|||
END DO |
|||
END FUNCTION SHUFFLE |
|||
! Compare two arrays element by element |
|||
FUNCTION COMPARE_ARRAYS(ARRAY_1, ARRAY_2) |
|||
INTEGER, DIMENSION(:) :: ARRAY_1, ARRAY_2 |
|||
LOGICAL :: COMPARE_ARRAYS |
|||
INTEGER :: I |
|||
DO I=1,SIZE(ARRAY_1) |
|||
IF (ARRAY_1(I) .NE. ARRAY_2(I)) THEN |
|||
COMPARE_ARRAYS = .FALSE. |
|||
RETURN |
|||
END IF |
|||
END DO |
|||
COMPARE_ARRAYS = .TRUE. |
|||
END FUNCTION COMPARE_ARRAYS |
|||
! Generate a deck/array of consecutive integers |
|||
FUNCTION GEN_DECK(DECK_SIZE) |
|||
INTEGER, INTENT(IN) :: DECK_SIZE |
|||
INTEGER, DIMENSION(DECK_SIZE) :: GEN_DECK |
|||
INTEGER :: I |
|||
GEN_DECK = (/(I, I=1,DECK_SIZE)/) |
|||
END FUNCTION GEN_DECK |
|||
END MODULE PERFECT_SHUFFLE |
|||
! Program to demonstrate the perfect shuffle algorithm |
|||
! for various deck sizes |
|||
PROGRAM DEMO_PERFECT_SHUFFLE |
|||
USE PERFECT_SHUFFLE |
|||
IMPLICIT NONE |
|||
INTEGER, PARAMETER, DIMENSION(7) :: DECK_SIZES = (/8, 24, 52, 100, 1020, 1024, 10000/) |
|||
INTEGER, DIMENSION(:), ALLOCATABLE :: DECK, SHUFFLED |
|||
INTEGER :: I, COUNTER |
|||
WRITE(*,'(A, A, A)') "input (deck size)", " | ", "output (number of shuffles required)" |
|||
WRITE(*,*) REPEAT("-", 55) |
|||
DO I=1, SIZE(DECK_SIZES) |
|||
IF (I .GT. 1) THEN |
|||
DEALLOCATE(DECK) |
|||
DEALLOCATE(SHUFFLED) |
|||
END IF |
|||
ALLOCATE(DECK(DECK_SIZES(I))) |
|||
ALLOCATE(SHUFFLED(DECK_SIZES(I))) |
|||
DECK = GEN_DECK(DECK_SIZES(I)) |
|||
SHUFFLED = SHUFFLE(DECK) |
|||
COUNTER = 1 |
|||
DO WHILE (.NOT. COMPARE_ARRAYS(DECK, SHUFFLED)) |
|||
SHUFFLED = SHUFFLE(SHUFFLED) |
|||
COUNTER = COUNTER + 1 |
|||
END DO |
|||
WRITE(*,'(I17, A, I35)') DECK_SIZES(I), " | ", COUNTER |
|||
END DO |
|||
END PROGRAM DEMO_PERFECT_SHUFFLE</syntaxhighlight> |
|||
<pre> |
|||
input (deck size) | output (number of shuffles required) |
|||
------------------------------------------------------- |
|||
8 | 3 |
|||
24 | 11 |
|||
52 | 8 |
|||
100 | 30 |
|||
1020 | 1018 |
|||
1024 | 10 |
|||
10000 | 300 |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">function is_in_order( d() as uinteger ) as boolean |
|||
'tests if a deck is in order |
|||
for i as uinteger = lbound(d) to ubound(d)-1 |
|||
if d(i) > d(i+1) then return false |
|||
next i |
|||
return true |
|||
end function |
|||
sub init_deck( d() as uinteger ) |
|||
for i as uinteger = 1 to ubound(d) |
|||
d(i) = i |
|||
next i |
|||
return |
|||
end sub |
|||
sub shuffle( d() as uinteger ) |
|||
'does a faro shuffle of the deck |
|||
dim as integer n = ubound(d), i |
|||
dim as integer b( 1 to n ) |
|||
for i = 1 to n/2 |
|||
b(2*i-1) = d(i) |
|||
b(2*i) = d(n/2+i) |
|||
next i |
|||
for i = 1 to n |
|||
d(i) = b(i) |
|||
next i |
|||
return |
|||
end sub |
|||
function shufs_needed( size as integer ) as uinteger |
|||
dim as uinteger d(1 to size), s = 0 |
|||
init_deck(d()) |
|||
do |
|||
shuffle(d()) |
|||
s+=1 |
|||
if is_in_order(d()) then exit do |
|||
loop |
|||
return s |
|||
end function |
|||
dim as uinteger tests(1 to 7) = {8, 24, 52, 100, 1020, 1024, 10000}, i |
|||
for i = 1 to 7 |
|||
print tests(i);" cards require "; shufs_needed(tests(i)); " shuffles." |
|||
next i</syntaxhighlight> |
|||
{{out}}<pre> |
|||
8 cards require 3 shuffles. |
|||
24 cards require 11 shuffles. |
|||
52 cards require 8 shuffles. |
|||
100 cards require 30 shuffles. |
|||
1020 cards require 1018 shuffles. |
|||
1024 cards require 10 shuffles. |
|||
10000 cards require 300 shuffles. |
|||
</pre> |
|||
=={{header|Go}}== |
|||
<syntaxhighlight lang="go">package main |
|||
import "fmt" |
|||
type Deck struct { |
|||
Cards []int |
|||
length int |
|||
} |
|||
func NewDeck(deckSize int) (res *Deck){ |
|||
if deckSize % 2 != 0{ |
|||
panic("Deck size must be even") |
|||
} |
|||
res = new(Deck) |
|||
res.Cards = make([]int, deckSize) |
|||
res.length = deckSize |
|||
for i,_ := range res.Cards{ |
|||
res.Cards[i] = i |
|||
} |
|||
return |
|||
} |
|||
func (d *Deck)shuffleDeck(){ |
|||
tmp := make([]int,d.length) |
|||
for i := 0;i <d.length/2;i++ { |
|||
tmp[i*2] = d.Cards[i] |
|||
tmp[i*2+1] = d.Cards[d.length / 2 + i] |
|||
} |
|||
d.Cards = tmp |
|||
} |
|||
func (d *Deck) isEqualTo(c Deck) (res bool) { |
|||
if d.length != c.length { |
|||
panic("Decks aren't equally sized") |
|||
} |
|||
res = true |
|||
for i, v := range d.Cards{ |
|||
if v != c.Cards[i] { |
|||
res = false |
|||
} |
|||
} |
|||
return |
|||
} |
|||
func main(){ |
|||
for _,v := range []int{8,24,52,100,1020,1024,10000} { |
|||
fmt.Printf("Cards count: %d, shuffles required: %d\n",v,ShufflesRequired(v)) |
|||
} |
|||
} |
|||
func ShufflesRequired(deckSize int)(res int){ |
|||
deck := NewDeck(deckSize) |
|||
Ref := *deck |
|||
deck.shuffleDeck() |
|||
res++ |
|||
for ;!deck.isEqualTo(Ref);deck.shuffleDeck(){ |
|||
res++ |
|||
} |
|||
return |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Cards count: 8, shuffles required: 3 |
|||
Cards count: 24, shuffles required: 11 |
|||
Cards count: 52, shuffles required: 8 |
|||
Cards count: 100, shuffles required: 30 |
|||
Cards count: 1020, shuffles required: 1018 |
|||
Cards count: 1024, shuffles required: 10 |
|||
Cards count: 10000, shuffles required: 300 </pre> |
|||
=={{header|Haskell}}== |
|||
<syntaxhighlight lang="haskell">shuffle :: [a] -> [a] |
|||
shuffle lst = let (a,b) = splitAt (length lst `div` 2) lst |
|||
in foldMap (\(x,y) -> [x,y]) $ zip a b |
|||
findCycle :: Eq a => (a -> a) -> a -> [a] |
|||
findCycle f x = takeWhile (/= x) $ iterate f (f x) |
|||
main = mapM_ report [ 8, 24, 52, 100, 1020, 1024, 10000 ] |
|||
where |
|||
report n = putStrLn ("deck of " ++ show n ++ " cards: " |
|||
++ show (countSuffles n) ++ " shuffles!") |
|||
countSuffles n = 1 + length (findCycle shuffle [1..n])</syntaxhighlight> |
|||
{{out}} |
|||
<pre>deck of 8 cards: 3 shuffles! |
|||
deck of 24 cards: 11 shuffles! |
|||
deck of 52 cards: 8 shuffles! |
|||
deck of 100 cards: 30 shuffles! |
|||
deck of 1020 cards: 1018 shuffles! |
|||
deck of 1024 cards: 10 shuffles! |
|||
deck of 10000 cards: 300 shuffles! |
|||
</pre> |
|||
=={{header|J}}== |
|||
The shuffle routine: |
|||
<syntaxhighlight lang="j"> shuf=: /: $ /:@$ 0 1"_</syntaxhighlight> |
|||
Here, the phrase ($ $ 0 1"_) would generate a sequence of 0s and 1s the same length as the argument sequence: |
|||
<syntaxhighlight lang="j"> ($ $ 0 1"_) 'abcdef' |
|||
0 1 0 1 0 1</syntaxhighlight> |
|||
And we can use ''grade up'' <code>(/:)</code> to find the indices which would sort the argument sequence so that the values in the positions corresponding to our generated zeros would come before the values in the positions corresponding to our ones. |
|||
<syntaxhighlight lang="j"> /: ($ $ 0 1"_) 'abcdef' |
|||
0 2 4 1 3 5</syntaxhighlight> |
|||
But we can use ''grade up'' again to find what would have been the original permutation (''grade up'' is a self inverting function for this domain). |
|||
<syntaxhighlight lang="j"> /:/: ($ $ 0 1"_) 'abcdef' |
|||
0 3 1 4 2 5</syntaxhighlight> |
|||
And, that means it can also sort the original sequence into that order: |
|||
<syntaxhighlight lang="j"> shuf 'abcdef' |
|||
adbecf |
|||
shuf 'abcdefgh' |
|||
aebfcgdh</syntaxhighlight> |
|||
And this will work for sequences of arbitrary length. |
|||
(The rest of the implementation of <code>shuf</code> is pure syntactic sugar - you can use J's [[j:Vocabulary/Dissect|dissect]] and [[j:Scripts/Tracer|trace]] facilities to see the details if you are trying to learn the language.) |
|||
Meanwhile, the cycle length routine could look like this: |
|||
<syntaxhighlight lang="j"> shuflen=: [: *./ #@>@C.@shuf@i.</syntaxhighlight> |
|||
Here, we first generate a list of integers of the required length in their natural order. We then reorder them using our <code>shuf</code> function, find the [[j:Vocabulary/ccapdot|cycles]] which result, find the lengths of each of these cycles then find the least common multiple of those lengths. |
|||
So here is the task example (with most of the middle trimmed out to avoid crashing the rosettacode wiki implementation): |
|||
<syntaxhighlight lang="j"> shuflen"0 }.2*i.5000 |
|||
1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 20 14 12 23 21 8 52 20 18 ... 4278 816 222 1332 384</syntaxhighlight> |
|||
Task example: |
|||
<syntaxhighlight lang="j"> ('deck size';'required shuffles'),(; shuflen)&> 8 24 52 100 1020 1024 10000 |
|||
┌─────────┬─────────────────┐ |
|||
│deck size│required shuffles│ |
|||
├─────────┼─────────────────┤ |
|||
│8 │3 │ |
|||
├─────────┼─────────────────┤ |
|||
│24 │11 │ |
|||
├─────────┼─────────────────┤ |
|||
│52 │8 │ |
|||
├─────────┼─────────────────┤ |
|||
│100 │30 │ |
|||
├─────────┼─────────────────┤ |
|||
│1020 │1018 │ |
|||
├─────────┼─────────────────┤ |
|||
│1024 │10 │ |
|||
├─────────┼─────────────────┤ |
|||
│10000 │300 │ |
|||
└─────────┴─────────────────┘</syntaxhighlight> |
|||
Note that the implementation of <code>shuf</code> defines a behavior for odd length "decks". Experimentation shows that cycle length for an odd length deck is often the same as the cycle length for an even length deck which is one "card" longer. |
|||
=={{header|Java}}== |
|||
{{works with|Java|8}} |
|||
<syntaxhighlight lang="java">import java.util.Arrays; |
|||
import java.util.stream.IntStream; |
|||
public class PerfectShuffle { |
|||
public static void main(String[] args) { |
|||
int[] sizes = {8, 24, 52, 100, 1020, 1024, 10_000}; |
|||
for (int size : sizes) |
|||
System.out.printf("%5d : %5d%n", size, perfectShuffle(size)); |
|||
} |
|||
static int perfectShuffle(int size) { |
|||
if (size % 2 != 0) |
|||
throw new IllegalArgumentException("size must be even"); |
|||
int half = size / 2; |
|||
int[] a = IntStream.range(0, size).toArray(); |
|||
int[] original = a.clone(); |
|||
int[] aa = new int[size]; |
|||
for (int count = 1; true; count++) { |
|||
System.arraycopy(a, 0, aa, 0, size); |
|||
for (int i = 0; i < half; i++) { |
|||
a[2 * i] = aa[i]; |
|||
a[2 * i + 1] = aa[i + half]; |
|||
} |
|||
if (Arrays.equals(a, original)) |
|||
return count; |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
<pre> 8 : 3 |
|||
24 : 11 |
|||
52 : 8 |
|||
100 : 30 |
|||
1020 : 1018 |
|||
1024 : 10 |
|||
10000 : 300</pre> |
|||
=={{header|JavaScript}}== |
|||
===ES6=== |
|||
<syntaxhighlight lang="javascript">(() => { |
|||
'use strict'; |
|||
// shuffleCycleLength :: Int -> Int |
|||
const shuffleCycleLength = deckSize => |
|||
firstCycle(shuffle, range(1, deckSize)) |
|||
.all.length; |
|||
// shuffle :: [a] -> [a] |
|||
const shuffle = xs => |
|||
concat(zip.apply(null, splitAt(div(length(xs), 2), xs))); |
|||
// firstycle :: Eq a => (a -> a) -> a -> [a] |
|||
const firstCycle = (f, x) => |
|||
until( |
|||
m => EqArray(x, m.current), |
|||
m => { |
|||
const fx = f(m.current); |
|||
return { |
|||
current: fx, |
|||
all: m.all.concat([fx]) |
|||
}; |
|||
}, { |
|||
current: f(x), |
|||
all: [x] |
|||
} |
|||
); |
|||
// Two arrays equal ? |
|||
// EqArray :: [a] -> [b] -> Bool |
|||
const EqArray = (xs, ys) => { |
|||
const [nx, ny] = [xs.length, ys.length]; |
|||
return nx === ny ? ( |
|||
nx > 0 ? ( |
|||
xs[0] === ys[0] && EqArray(xs.slice(1), ys.slice(1)) |
|||
) : true |
|||
) : false; |
|||
}; |
|||
// GENERIC FUNCTIONS |
|||
// zip :: [a] -> [b] -> [(a,b)] |
|||
const zip = (xs, ys) => |
|||
xs.slice(0, Math.min(xs.length, ys.length)) |
|||
.map((x, i) => [x, ys[i]]); |
|||
// concat :: [[a]] -> [a] |
|||
const concat = xs => [].concat.apply([], xs); |
|||
// splitAt :: Int -> [a] -> ([a],[a]) |
|||
const splitAt = (n, xs) => [xs.slice(0, n), xs.slice(n)]; |
|||
// div :: Num -> Num -> Int |
|||
const div = (x, y) => Math.floor(x / y); |
|||
// until :: (a -> Bool) -> (a -> a) -> a -> a |
|||
const until = (p, f, x) => { |
|||
const go = x => p(x) ? x : go(f(x)); |
|||
return go(x); |
|||
} |
|||
// range :: Int -> Int -> [Int] |
|||
const range = (m, n) => |
|||
Array.from({ |
|||
length: Math.floor(n - m) + 1 |
|||
}, (_, i) => m + i); |
|||
// length :: [a] -> Int |
|||
// length :: Text -> Int |
|||
const length = xs => xs.length; |
|||
// maximumBy :: (a -> a -> Ordering) -> [a] -> a |
|||
const maximumBy = (f, xs) => |
|||
xs.reduce((a, x) => a === undefined ? x : ( |
|||
f(x, a) > 0 ? x : a |
|||
), undefined); |
|||
// transpose :: [[a]] -> [[a]] |
|||
const transpose = xs => |
|||
xs[0].map((_, iCol) => xs.map((row) => row[iCol])); |
|||
// show :: a -> String |
|||
const show = x => JSON.stringify(x, null, 2); |
|||
// replicateS :: Int -> String -> String |
|||
const replicateS = (n, s) => { |
|||
let v = s, |
|||
o = ''; |
|||
if (n < 1) return o; |
|||
while (n > 1) { |
|||
if (n & 1) o = o.concat(v); |
|||
n >>= 1; |
|||
v = v.concat(v); |
|||
} |
|||
return o.concat(v); |
|||
}; |
|||
// justifyRight :: Int -> Char -> Text -> Text |
|||
const justifyRight = (n, cFiller, strText) => |
|||
n > strText.length ? ( |
|||
(replicateS(n, cFiller) + strText) |
|||
.slice(-n) |
|||
) : strText; |
|||
// TEST |
|||
return transpose(transpose([ |
|||
['Deck', 'Shuffles'] |
|||
].concat( |
|||
[8, 24, 52, 100, 1020, 1024, 10000] |
|||
.map(n => [n.toString(), shuffleCycleLength(n) |
|||
.toString() |
|||
]))) |
|||
.map(col => { // Right-justified number columns |
|||
const width = length( |
|||
maximumBy((a, b) => length(a) - length(b), col) |
|||
) + 2; |
|||
return col.map(x => justifyRight(width, ' ', x)); |
|||
})) |
|||
.map(row => row.join('')) |
|||
.join('\n'); |
|||
})();</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> Deck Shuffles |
|||
8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
A small point of interest in the following is the `recurrence` function as it is generic. |
|||
<syntaxhighlight lang="jq">def perfect_shuffle: |
|||
. as $a |
|||
| if (length % 2) == 1 then "cannot perform perfect shuffle on odd-length array" | error |
|||
else (length / 2) as $mid |
|||
| reduce range(0; $mid) as $i (null; |
|||
.[2*$i] = $a[$i] |
|||
| .[2*$i + 1] = $a[$mid+$i] ) |
|||
end; |
|||
# How many iterations of f are required to get back to . ? |
|||
def recurrence(f): |
|||
def r: |
|||
# input: [$init, $current, $count] |
|||
(.[1]|f) as $next |
|||
| if .[0] == $next then .[-1] + 1 |
|||
else [.[0], $next, .[-1]+1] | r |
|||
end; |
|||
[., ., 0] | r; |
|||
def count_perfect_shuffles: |
|||
[range(0;.)] | recurrence(perfect_shuffle); |
|||
(8, 24, 52, 100, 1020, 1024, 10000, 100000) |
|||
| [., count_perfect_shuffles]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[8,3] |
|||
[24,11] |
|||
[52,8] |
|||
[100,30] |
|||
[1020,1018] |
|||
[1024,10] |
|||
[10000,300] |
|||
[100000,540] |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
<syntaxhighlight lang="julia">using Printf |
|||
function perfect_shuffle(a::Array)::Array |
|||
if isodd(length(a)) error("cannot perform perfect shuffle on odd-length array") end |
|||
rst = zeros(a) |
|||
mid = div(length(a), 2) |
|||
for i in 1:mid |
|||
rst[2i-1], rst[2i] = a[i], a[mid+i] |
|||
end |
|||
return rst |
|||
end |
|||
function count_perfect_shuffles(decksize::Int)::Int |
|||
a = collect(1:decksize) |
|||
b, c = perfect_shuffle(a), 1 |
|||
while a != b |
|||
b = perfect_shuffle(b) |
|||
c += 1 |
|||
end |
|||
return c |
|||
end |
|||
println(" Deck n.Shuffles") |
|||
for i in (8, 24, 52, 100, 1020, 1024, 10000, 100000) |
|||
count = count_perfect_shuffles(i) |
|||
@printf("%7i%7i\n", i, count) |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre> Deck n.Shuffles |
|||
8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300 |
|||
100000 540</pre> |
|||
=={{header|Kotlin}}== |
|||
<syntaxhighlight lang="scala">// version 1.1.2 |
|||
fun areSame(a: IntArray, b: IntArray): Boolean { |
|||
for (i in 0 until a.size) if (a[i] != b[i]) return false |
|||
return true |
|||
} |
|||
fun perfectShuffle(a: IntArray): IntArray { |
|||
var b = IntArray(a.size) |
|||
val hSize = a.size / 2 |
|||
for (i in 0 until hSize) b[i * 2] = a[i] |
|||
var j = 1 |
|||
for (i in hSize until a.size) { |
|||
b[j] = a[i] |
|||
j += 2 |
|||
} |
|||
return b |
|||
} |
|||
fun countShuffles(a: IntArray): Int { |
|||
require(a.size >= 2 && a.size % 2 == 0) |
|||
var b = a |
|||
var count = 0 |
|||
while (true) { |
|||
val c = perfectShuffle(b) |
|||
count++ |
|||
if (areSame(a, c)) return count |
|||
b = c |
|||
} |
|||
} |
|||
fun main(args: Array<String>) { |
|||
println("Deck size Num shuffles") |
|||
println("--------- ------------") |
|||
val sizes = intArrayOf(8, 24, 52, 100, 1020, 1024, 10000) |
|||
for (size in sizes) { |
|||
val a = IntArray(size) { it } |
|||
val count = countShuffles(a) |
|||
println("${"%-9d".format(size)} $count") |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Deck size Num shuffles |
|||
--------- ------------ |
|||
8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300 |
|||
</pre> |
|||
=={{header|Lua}}== |
|||
<syntaxhighlight lang="lua">-- Perform weave shuffle |
|||
function shuffle (cards) |
|||
local pile1, pile2 = {}, {} |
|||
for card = 1, #cards / 2 do table.insert(pile1, cards[card]) end |
|||
for card = (#cards / 2) + 1, #cards do table.insert(pile2, cards[card]) end |
|||
cards = {} |
|||
for card = 1, #pile1 do |
|||
table.insert(cards, pile1[card]) |
|||
table.insert(cards, pile2[card]) |
|||
end |
|||
return cards |
|||
end |
|||
-- Return boolean indicating whether or not the cards are in order |
|||
function inOrder (cards) |
|||
for k, v in pairs(cards) do |
|||
if k ~= v then return false end |
|||
end |
|||
return true |
|||
end |
|||
-- Count the number of shuffles needed before the cards are in order again |
|||
function countShuffles (deckSize) |
|||
local deck, count = {}, 0 |
|||
for i = 1, deckSize do deck[i] = i end |
|||
repeat |
|||
deck = shuffle(deck) |
|||
count = count + 1 |
|||
until inOrder(deck) |
|||
return count |
|||
end |
|||
-- Main procedure |
|||
local testCases = {8, 24, 52, 100, 1020, 1024, 10000} |
|||
print("Input", "Output") |
|||
for _, case in pairs(testCases) do print(case, countShuffles(case)) end</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Input Output |
|||
8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">shuffle[deck_] := Apply[Riffle, TakeDrop[deck, Length[deck]/2]]; |
|||
shuffleCount[n_] := Block[{count=0}, NestWhile[shuffle, shuffle[Range[n]], (count++; OrderedQ[#] )&];count]; |
|||
Map[shuffleCount, {8, 24, 52, 100, 1020, 1024, 10000}]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{3, 11, 8, 30, 1018, 10, 300}</pre> |
|||
=={{header|MATLAB}}== |
|||
PerfectShuffle.m: |
|||
<syntaxhighlight lang="matlab">function [New]=PerfectShuffle(Nitems, Nturns) |
|||
if mod(Nitems,2)==0 %only if even number |
|||
X=1:Nitems; %define deck |
|||
for c=1:Nturns %defines one shuffle |
|||
X=reshape(X,Nitems/2,2)'; %split the deck in two and stack halves |
|||
X=X(:)'; %mix the halves |
|||
end |
|||
New=X; %result of multiple shufflings |
|||
end</syntaxhighlight> |
|||
Main: |
|||
<syntaxhighlight lang="matlab">Result=[]; %vector to store results |
|||
Q=[8, 24, 52, 100, 1020, 1024, 10000]; %queries |
|||
for n=Q %for each query |
|||
Same=0; %initialize comparison |
|||
T=0; %initialize number of shuffles |
|||
while ~Same %while the result is not the original query |
|||
T=T+1; %one more shuffle |
|||
R=PerfectShuffle(n,T); %result of shuffling the query |
|||
Same=~(any(R-(1:n))); %same vector as the query |
|||
end %when getting the same vector |
|||
Result=[Result;T]; %collect results |
|||
end |
|||
disp([Q', Result])</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300</pre> |
|||
=={{header|Modula-2}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="modula2">MODULE PerfectShuffle; |
|||
FROM FormatString IMPORT FormatString; |
|||
FROM Storage IMPORT ALLOCATE,DEALLOCATE; |
|||
FROM SYSTEM IMPORT ADDRESS,TSIZE; |
|||
FROM Terminal IMPORT WriteString,WriteLn,ReadChar; |
|||
PROCEDURE WriteCard(c : CARDINAL); |
|||
VAR buf : ARRAY[0..15] OF CHAR; |
|||
BEGIN |
|||
FormatString("%c", buf, c); |
|||
WriteString(buf) |
|||
END WriteCard; |
|||
PROCEDURE Init(VAR arr : ARRAY OF INTEGER); |
|||
VAR i : CARDINAL; |
|||
BEGIN |
|||
FOR i:=0 TO HIGH(arr) DO |
|||
arr[i] := i + 1 |
|||
END |
|||
END Init; |
|||
PROCEDURE PerfectShuffle(VAR arr : ARRAY OF INTEGER); |
|||
PROCEDURE Inner(ti : CARDINAL); |
|||
VAR |
|||
tv : INTEGER; |
|||
tp,tn,n : CARDINAL; |
|||
BEGIN |
|||
n := HIGH(arr); |
|||
tn := ti; |
|||
tv := arr[ti]; |
|||
REPEAT |
|||
tp := tn; |
|||
IF tp MOD 2 = 0 THEN |
|||
tn := tp / 2 |
|||
ELSE |
|||
tn := (n+1)/2+tp/2 |
|||
END; |
|||
arr[tp] := arr[tn]; |
|||
UNTIL tn = ti; |
|||
arr[tp] := tv |
|||
END Inner; |
|||
VAR |
|||
done : BOOLEAN; |
|||
i,c : CARDINAL; |
|||
BEGIN |
|||
c := 0; |
|||
Init(arr); |
|||
REPEAT |
|||
i := 1; |
|||
WHILE i <= (HIGH(arr)/2) DO |
|||
Inner(i); |
|||
INC(i,2) |
|||
END; |
|||
INC(c); |
|||
done := TRUE; |
|||
FOR i:=0 TO HIGH(arr) DO |
|||
IF arr[i] # INT(i+1) THEN |
|||
done := FALSE; |
|||
BREAK |
|||
END |
|||
END |
|||
UNTIL done; |
|||
WriteCard(HIGH(arr)+1); |
|||
WriteString(": "); |
|||
WriteCard(c); |
|||
WriteLn |
|||
END PerfectShuffle; |
|||
(* Main *) |
|||
VAR |
|||
v8 : ARRAY[1..8] OF INTEGER; |
|||
v24 : ARRAY[1..24] OF INTEGER; |
|||
v52 : ARRAY[1..52] OF INTEGER; |
|||
v100 : ARRAY[1..100] OF INTEGER; |
|||
v1020 : ARRAY[1..1020] OF INTEGER; |
|||
v1024 : ARRAY[1..1024] OF INTEGER; |
|||
v10000 : ARRAY[1..10000] OF INTEGER; |
|||
BEGIN |
|||
PerfectShuffle(v8); |
|||
PerfectShuffle(v24); |
|||
PerfectShuffle(v52); |
|||
PerfectShuffle(v100); |
|||
PerfectShuffle(v1020); |
|||
PerfectShuffle(v1024); |
|||
PerfectShuffle(v10000); |
|||
ReadChar |
|||
END PerfectShuffle.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>8: 3 |
|||
24: 11 |
|||
52: 8 |
|||
100: 30 |
|||
1020: 1018 |
|||
1024: 10 |
|||
10000: 300</pre> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">import sequtils, strutils |
|||
proc newValList(size: Positive): seq[int] = |
|||
if (size and 1) != 0: |
|||
raise newException(ValueError, "size must be even.") |
|||
result = toSeq(1..size) |
|||
func shuffled(list: seq[int]): seq[int] = |
|||
result.setLen(list.len) |
|||
let half = list.len div 2 |
|||
for i in 0..<half: |
|||
result[2 * i] = list[i] |
|||
result[2 * i + 1] = list[half + i] |
|||
for size in [8, 24, 52, 100, 1020, 1024, 10000]: |
|||
let initList = newValList(size) |
|||
var valList = initList |
|||
var count = 0 |
|||
while true: |
|||
inc count |
|||
valList = shuffled(valList) |
|||
if valList == initList: |
|||
break |
|||
echo ($size).align(5), ": ", ($count).align(4)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 8: 3 |
|||
24: 11 |
|||
52: 8 |
|||
100: 30 |
|||
1020: 1018 |
|||
1024: 10 |
|||
10000: 300</pre> |
|||
=={{header|Oforth}}== |
|||
<syntaxhighlight lang="oforth">: shuffle(l) l size 2 / dup l left swap l right zip expand ; |
|||
: nbShuffles(l) 1 l while( shuffle dup l <> ) [ 1 under+ ] drop ;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
>[ 8, 24, 52, 100, 1020, 1024, 10000 ] map(#[ seq nbShuffles ]) . |
|||
[3, 11, 8, 30, 1018, 10, 300] ok |
|||
</pre> |
|||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
{{improve|PARI/GP|The task description was updated; please update this solution accordingly and then remove this template.}} |
|||
<lang parigp>magic(v)=vector(#v,i,v[if(i%2,1,#v/2)+i\2]); |
|||
<syntaxhighlight lang="parigp">magic(v)=vector(#v,i,v[if(i%2,1,#v/2)+i\2]); |
|||
shuffles_slow(n)=my(v=[1..n],o=v,s=1);while((v=magic(v))!=o,s++);s; |
shuffles_slow(n)=my(v=[1..n],o=v,s=1);while((v=magic(v))!=o,s++);s; |
||
shuffles(n)=znorder(Mod(2,n-1)); |
shuffles(n)=znorder(Mod(2,n-1)); |
||
vector(5000,n,shuffles_slow(2*n))</ |
vector(5000,n,shuffles_slow(2*n))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>%1 = [1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, |
<pre>%1 = [1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, |
||
Line 49: | Line 1,942: | ||
(By default gp won't show more than 25 lines of output, though an arbitrary amount can be printed or written to a file; use <code>print</code>, <code>write</code>, or <code>default(lines, 100)</code> to show more.) |
(By default gp won't show more than 25 lines of output, though an arbitrary amount can be printed or written to a file; use <code>print</code>, <code>write</code>, or <code>default(lines, 100)</code> to show more.) |
||
=={{header|Perl}}== |
|||
<syntaxhighlight lang="perl">use v5.36; |
|||
use List::Util 'all'; |
|||
sub perfect_shuffle (@deck) { |
|||
my $middle = @deck / 2; |
|||
map { @deck[$_, $_ + $middle] } 0..$middle-1; |
|||
} |
|||
for my $size (8, 24, 52, 100, 1020, 1024, 10000) { |
|||
my @shuffled = my @deck = 1..$size; |
|||
my $n; |
|||
do { $n++; @shuffled = perfect_shuffle @shuffled } |
|||
until all { $shuffled[$_] == $deck[$_] } 0..$#shuffled; |
|||
printf "%5d cards: %4d\n", $size, $n; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8 cards: 3 |
|||
24 cards: 11 |
|||
52 cards: 8 |
|||
100 cards: 30 |
|||
1020 cards: 1018 |
|||
1024 cards: 10 |
|||
10000 cards: 300 |
|||
</pre> |
|||
=={{header|Phix}}== |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">perfect_shuffle</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">deck</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">deck</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">mp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">mp</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">deck</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">deck</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">mp</span><span style="color: #0000FF;">]</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">testsizes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">24</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">52</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">100</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1020</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1024</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10000</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testsizes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">deck</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testsizes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">work</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perfect_shuffle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">deck</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">work</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">deck</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000000;">work</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perfect_shuffle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">work</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%5d cards: %4d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">testsizes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
8 cards: 3 |
|||
24 cards: 11 |
|||
52 cards: 8 |
|||
100 cards: 30 |
|||
1020 cards: 1018 |
|||
1024 cards: 10 |
|||
10000 cards: 300 |
|||
</pre> |
|||
=={{header|Picat}}== |
|||
A perfect shuffle can be done in two ways: |
|||
* '''in''': first card in top half is the first card in the new deck |
|||
* '''out''': first card in bottom half is the first card in the new deck |
|||
The method used here supports both shuffle types. The task states an '''out''' shuffling. |
|||
===Out shuffle=== |
|||
<syntaxhighlight lang="picat">go => |
|||
member(N,[8,24,52,100,1020,1024,10_000]), |
|||
println(n=N), |
|||
InOut = out, % in/out shuffling |
|||
println(inOut=InOut), |
|||
Print = cond(N < 100, true,false), |
|||
if Print then |
|||
println(1..N), |
|||
end, |
|||
Count = show_all_shuffles(N,InOut,Print), |
|||
println(count=Count), |
|||
nl, |
|||
fail, |
|||
nl. |
|||
% |
|||
% Show all the shuffles |
|||
% |
|||
show_all_shuffles(N,InOut) = show_all_shuffles(N,InOut,false). |
|||
show_all_shuffles(N,InOut,Print) = Count => |
|||
Order = 1..N, |
|||
Perfect1 = perfect_shuffle(1..N,InOut), |
|||
Perfect = copy_term(Perfect1), |
|||
if Print == true then |
|||
println(Perfect) |
|||
end, |
|||
Count = 1, |
|||
while (Perfect != Order) |
|||
Perfect := [Perfect1[Perfect[I]] : I in 1..N], |
|||
if Print == true then |
|||
println(Perfect) |
|||
end, |
|||
Count := Count + 1 |
|||
end. |
|||
% |
|||
% Perfect shuffle a list |
|||
% |
|||
% InOut = in|out |
|||
% in: first card in Top half is the first card in the new deck |
|||
% out: first card in Bottom half is the first card in the new deck |
|||
% |
|||
perfect_shuffle(List,InOut) = Perfect => |
|||
[Top,Bottom] = split_deck(List,InOut), |
|||
if InOut = out then |
|||
Perfect = zip2(Top,Bottom) |
|||
else |
|||
Perfect = zip2(Bottom,Top) |
|||
end. |
|||
% |
|||
% split the deck in two "halves" |
|||
% |
|||
% For odd out shuffles, we have to adjust the |
|||
% range of the top and bottom. |
|||
% |
|||
split_deck(L,InOut) = [Top,Bottom] => |
|||
N = L.len, |
|||
if InOut = out, N mod 2 = 1 then |
|||
Top = 1..(N div 2)+1, |
|||
Bottom = (N div 2)+2..N |
|||
else |
|||
Top = 1..(N div 2), |
|||
Bottom = (N div 2)+1..N |
|||
end. |
|||
% |
|||
% If L1 and L2 has uneven lengths, we add the odd element last |
|||
% in the resulting list. |
|||
% |
|||
zip2(L1,L2) = R => |
|||
L1Len = L1.len, |
|||
L2Len = L2.len, |
|||
R1 = [], |
|||
foreach(I in 1..min(L1Len,L2Len)) |
|||
R1 := R1 ++ [L1[I],L2[I]] |
|||
end, |
|||
if L1Len < L2Len then |
|||
R1 := R1 ++ [L2[L2Len]] |
|||
elseif L1Len > L2Len then |
|||
R1 := R1 ++ [L1[L1Len]] |
|||
end, |
|||
R = R1.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>n = 8 |
|||
inOut = out |
|||
[1,2,3,4,5,6,7,8] |
|||
[1,5,2,6,3,7,4,8] |
|||
[1,3,5,7,2,4,6,8] |
|||
[1,2,3,4,5,6,7,8] |
|||
count = 3 |
|||
n = 24 |
|||
inOut = out |
|||
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24] |
|||
[1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,11,23,12,24] |
|||
[1,7,13,19,2,8,14,20,3,9,15,21,4,10,16,22,5,11,17,23,6,12,18,24] |
|||
[1,4,7,10,13,16,19,22,2,5,8,11,14,17,20,23,3,6,9,12,15,18,21,24] |
|||
[1,14,4,17,7,20,10,23,13,3,16,6,19,9,22,12,2,15,5,18,8,21,11,24] |
|||
[1,19,14,9,4,22,17,12,7,2,20,15,10,5,23,18,13,8,3,21,16,11,6,24] |
|||
[1,10,19,5,14,23,9,18,4,13,22,8,17,3,12,21,7,16,2,11,20,6,15,24] |
|||
[1,17,10,3,19,12,5,21,14,7,23,16,9,2,18,11,4,20,13,6,22,15,8,24] |
|||
[1,9,17,2,10,18,3,11,19,4,12,20,5,13,21,6,14,22,7,15,23,8,16,24] |
|||
[1,5,9,13,17,21,2,6,10,14,18,22,3,7,11,15,19,23,4,8,12,16,20,24] |
|||
[1,3,5,7,9,11,13,15,17,19,21,23,2,4,6,8,10,12,14,16,18,20,22,24] |
|||
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24] |
|||
count = 11 |
|||
n = 52 |
|||
inOut = out |
|||
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52] |
|||
[1,27,2,28,3,29,4,30,5,31,6,32,7,33,8,34,9,35,10,36,11,37,12,38,13,39,14,40,15,41,16,42,17,43,18,44,19,45,20,46,21,47,22,48,23,49,24,50,25,51,26,52] |
|||
[1,14,27,40,2,15,28,41,3,16,29,42,4,17,30,43,5,18,31,44,6,19,32,45,7,20,33,46,8,21,34,47,9,22,35,48,10,23,36,49,11,24,37,50,12,25,38,51,13,26,39,52] |
|||
[1,33,14,46,27,8,40,21,2,34,15,47,28,9,41,22,3,35,16,48,29,10,42,23,4,36,17,49,30,11,43,24,5,37,18,50,31,12,44,25,6,38,19,51,32,13,45,26,7,39,20,52] |
|||
[1,17,33,49,14,30,46,11,27,43,8,24,40,5,21,37,2,18,34,50,15,31,47,12,28,44,9,25,41,6,22,38,3,19,35,51,16,32,48,13,29,45,10,26,42,7,23,39,4,20,36,52] |
|||
[1,9,17,25,33,41,49,6,14,22,30,38,46,3,11,19,27,35,43,51,8,16,24,32,40,48,5,13,21,29,37,45,2,10,18,26,34,42,50,7,15,23,31,39,47,4,12,20,28,36,44,52] |
|||
[1,5,9,13,17,21,25,29,33,37,41,45,49,2,6,10,14,18,22,26,30,34,38,42,46,50,3,7,11,15,19,23,27,31,35,39,43,47,51,4,8,12,16,20,24,28,32,36,40,44,48,52] |
|||
[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52] |
|||
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52] |
|||
count = 8 |
|||
n = 100 |
|||
inOut = out |
|||
count = 30 |
|||
n = 1020 |
|||
inOut = out |
|||
count = 1018 |
|||
n = 1024 |
|||
inOut = out |
|||
count = 10 |
|||
n = 10000 |
|||
inOut = out |
|||
count = 300</pre> |
|||
===In shuffle=== |
|||
Here's an example of an '''in''' shuffle. It takes 6 shuffles to get an 8 card deck back to its original order (compare with 3 for an out shuffle). |
|||
<syntaxhighlight lang="picat">main => |
|||
N = 8, |
|||
println(1..N), |
|||
InOut = in, % in shuffling |
|||
Count = show_all_shuffles(N,InOut,true), |
|||
println(count=Count), |
|||
nl.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1,2,3,4,5,6,7,8] |
|||
[5,1,6,2,7,3,8,4] |
|||
[7,5,3,1,8,6,4,2] |
|||
[8,7,6,5,4,3,2,1] |
|||
[4,8,3,7,2,6,1,5] |
|||
[2,4,6,8,1,3,5,7] |
|||
[1,2,3,4,5,6,7,8] |
|||
count = 6</pre> |
|||
===Uneven decks=== |
|||
The method supports decks of uneven lengths, here size 11 (using an out shuffle). |
|||
<syntaxhighlight lang="picat">main => |
|||
N = 11, |
|||
println(1..N), |
|||
InOut = out, % in/out shuffling |
|||
Count = show_all_shuffles(N,InOut,true), |
|||
println(count=Count), |
|||
nl.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[1,2,3,4,5,6,7,8,9,10,11] |
|||
[1,7,2,8,3,9,4,10,5,11,6] |
|||
[1,4,7,10,2,5,8,11,3,6,9] |
|||
[1,8,4,11,7,3,10,6,2,9,5] |
|||
[1,10,8,6,4,2,11,9,7,5,3] |
|||
[1,11,10,9,8,7,6,5,4,3,2] |
|||
[1,6,11,5,10,4,9,3,8,2,7] |
|||
[1,9,6,3,11,8,5,2,10,7,4] |
|||
[1,5,9,2,6,10,3,7,11,4,8] |
|||
[1,3,5,7,9,11,2,4,6,8,10] |
|||
[1,2,3,4,5,6,7,8,9,10,11] |
|||
count = 10</pre> |
|||
=={{header|PicoLisp}}== |
|||
<syntaxhighlight lang="picolisp">(de perfectShuffle (Lst) |
|||
(mapcan '((B A) (list A B)) |
|||
(cdr (nth Lst (/ (length Lst) 2))) |
|||
Lst ) ) |
|||
(for N (8 24 52 100 1020 1024 10000) |
|||
(let (Lst (range 1 N) L Lst Cnt 1) |
|||
(until (= Lst (setq L (perfectShuffle L))) |
|||
(inc 'Cnt) ) |
|||
(tab (5 6) N Cnt) ) )</syntaxhighlight> |
|||
Output: |
|||
<pre> 8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python"> |
||
import doctest |
import doctest |
||
import random |
import random |
||
Line 89: | Line 2,257: | ||
print("Length of the deck of cards | Perfect shuffles needed to obtain the same deck back") |
print("Length of the deck of cards | Perfect shuffles needed to obtain the same deck back") |
||
for length in |
for length in (8, 24, 52, 100, 1020, 1024, 10000): |
||
deck = list(range(length)) |
deck = list(range(length)) |
||
shuffles_needed = after_how_many_is_equal(magic_shuffle,deck,deck) |
shuffles_needed = after_how_many_is_equal(magic_shuffle,deck,deck) |
||
Line 98: | Line 2,266: | ||
main() |
main() |
||
</syntaxhighlight> |
|||
</lang> |
|||
More functional version of the same code: |
|||
<syntaxhighlight lang="python"> |
|||
""" |
|||
Brute force solution for the Perfect Shuffle problem. |
|||
See http://oeis.org/A002326 for possible improvements |
|||
""" |
|||
from functools import partial |
|||
from itertools import chain |
|||
from operator import eq |
|||
from typing import (Callable, |
|||
Iterable, |
|||
Iterator, |
|||
List, |
|||
TypeVar) |
|||
T = TypeVar('T') |
|||
def main(): |
|||
print("Deck length | Shuffles ") |
|||
for length in (8, 24, 52, 100, 1020, 1024, 10000): |
|||
deck = list(range(length)) |
|||
shuffles_needed = spin_number(deck, shuffle) |
|||
print(f"{length:<11} | {shuffles_needed}") |
|||
def shuffle(deck: List[T]) -> List[T]: |
|||
"""[1, 2, 3, 4] -> [1, 3, 2, 4]""" |
|||
half = len(deck) // 2 |
|||
return list(chain.from_iterable(zip(deck[:half], deck[half:]))) |
|||
def spin_number(source: T, |
|||
function: Callable[[T], T]) -> int: |
|||
""" |
|||
Applies given function to the source |
|||
until the result becomes equal to it, |
|||
returns the number of calls |
|||
""" |
|||
is_equal_source = partial(eq, source) |
|||
spins = repeat_call(function, source) |
|||
return next_index(is_equal_source, |
|||
spins, |
|||
start=1) |
|||
def repeat_call(function: Callable[[T], T], |
|||
value: T) -> Iterator[T]: |
|||
"""(f, x) -> f(x), f(f(x)), f(f(f(x))), ...""" |
|||
while True: |
|||
value = function(value) |
|||
yield value |
|||
def next_index(predicate: Callable[[T], bool], |
|||
iterable: Iterable[T], |
|||
start: int = 0) -> int: |
|||
""" |
|||
Returns index of the first element of the iterable |
|||
satisfying given condition |
|||
""" |
|||
for index, item in enumerate(iterable, start=start): |
|||
if predicate(item): |
|||
return index |
|||
if __name__ == "__main__": |
|||
main() |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>Deck length | Shuffles |
|||
8 | 3 |
|||
24 | 11 |
|||
52 | 8 |
|||
100 | 30 |
|||
1020 | 1018 |
|||
1024 | 10 |
|||
10000 | 300</pre> |
|||
Reversed shuffle or just calculate how many shuffles are needed: |
Reversed shuffle or just calculate how many shuffles are needed: |
||
< |
<syntaxhighlight lang="python">def mul_ord2(n): |
||
# directly calculate how many shuffles are needed to restore |
# directly calculate how many shuffles are needed to restore |
||
# initial order: 2^o mod(n-1) == 1 |
# initial order: 2^o mod(n-1) == 1 |
||
Line 124: | Line 2,370: | ||
for n in range(2, 10000, 2): |
for n in range(2, 10000, 2): |
||
#print(n, mul_ord2(n)) |
#print(n, mul_ord2(n)) |
||
print(n, shuffles(n))</ |
print(n, shuffles(n))</syntaxhighlight> |
||
=={{header| |
=={{header|Quackery}}== |
||
<syntaxhighlight lang="quackery"> [ [] swap |
|||
With an overwhelming urge to say that <code>math/number-theory</code> rocks! |
|||
times [ i^ join ] ] is deck ( n --> [ ) |
|||
<lang racket>#lang racket |
|||
(require math/number-theory) |
|||
[ dup size 2 / split swap |
|||
;; COMMENTS: Number of riffle shuffles of 2n+2 cards required to return a deck to initial state. |
|||
witheach |
|||
(define (A002326 2n+2) |
|||
[ swap i^ 2 * stuff ] ] is weave ( [ --> [ ) |
|||
(unit-group-order 2 (- 2n+2 1))) |
|||
[ 0 swap |
|||
deck dup |
|||
[ rot 1+ unrot |
|||
weave 2dup = until ] |
|||
2drop ] is shuffles ( n --> n ) |
|||
' [ 8 24 52 100 1020 1024 10000 ] |
|||
witheach |
|||
[ say "A deck of " |
|||
dup echo say " cards needs " |
|||
shuffles echo say " shuffles." |
|||
cr ]</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>A deck of 8 cards needs 3 shuffles. |
|||
A deck of 24 cards needs 11 shuffles. |
|||
A deck of 52 cards needs 8 shuffles. |
|||
A deck of 100 cards needs 30 shuffles. |
|||
A deck of 1020 cards needs 1018 shuffles. |
|||
A deck of 1024 cards needs 10 shuffles. |
|||
A deck of 10000 cards needs 300 shuffles. |
|||
</pre> |
|||
=={{header|R}}== |
|||
===Matrix solution=== |
|||
<syntaxhighlight lang="rsplus">wave.shuffle <- function(n) { |
|||
deck <- 1:n ## create the original deck |
|||
new.deck <- c(matrix(data = deck, ncol = 2, byrow = TRUE)) ## shuffle the deck once |
|||
counter <- 1 ## track the number of loops |
|||
## defining a loop that shuffles the new deck until identical with the original one |
|||
## and in the same time increses the counter with 1 per loop |
|||
while (!identical(deck, new.deck)) { ## logical condition |
|||
new.deck <- c(matrix(data = new.deck, ncol = 2, byrow = TRUE)) ## shuffle |
|||
counter <- counter + 1 ## add 1 to the number of loops |
|||
} |
|||
return(counter) ## final result - total number of loops until the condition is met |
|||
} |
|||
test.values <- c(8, 24, 52, 100, 1020, 1024, 10000) ## the set of the test values |
|||
test <- sapply(test.values, wave.shuffle) ## apply the wave.shuffle function on each element |
|||
names(test) <- test.values ## name the result |
|||
test ## print the result out</syntaxhighlight> |
|||
{{out}} |
|||
<pre>> test |
|||
8 24 52 100 1020 1024 10000 |
|||
3 11 8 30 1018 10 300</pre> |
|||
===Sequence solution=== |
|||
The previous solution exploits R's matrix construction; This solution exploits its array indexing. |
|||
<syntaxhighlight lang="rsplus">#A strict reading of the task description says that we need a function that does exactly one shuffle. |
|||
pShuffle <- function(deck) |
|||
{ |
|||
n <- length(deck)#Assumed even (as in task description). |
|||
shuffled <- array(n)#Maybe not as general as it could be, but the task said to use whatever was convenient. |
|||
shuffled[seq(from = 1, to = n, by = 2)] <- deck[seq(from = 1, to = n/2, by = 1)] |
|||
shuffled[seq(from = 2, to = n, by = 2)] <- deck[seq(from = 1 + n/2, to = n, by = 1)] |
|||
shuffled |
|||
} |
|||
task2 <- function(deck) |
|||
{ |
|||
shuffled <- deck |
|||
count <- 0 |
|||
repeat |
|||
{ |
|||
shuffled <- pShuffle(shuffled) |
|||
count <- count + 1 |
|||
if(all(shuffled == deck)) break |
|||
} |
|||
cat("It takes", count, "shuffles of a deck of size", length(deck), "to return to the original deck.","\n") |
|||
invisible(count)#For the unit tests. The task wanted this printed so we only return it invisibly. |
|||
} |
|||
#Tests - All done in one line. |
|||
mapply(function(x, y) task2(1:x) == y, c(8, 24, 52, 100, 1020, 1024, 10000), c(3, 11, 8, 30, 1018, 10, 300))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>> mapply(function(x, y) task2(1:x) == y, c(8, 24, 52, 100, 1020, 1024, 10000), c(3, 11, 8, 30, 1018, 10, 300)) |
|||
It takes 3 shuffles of a deck of size 8 to return to the original deck. |
|||
It takes 11 shuffles of a deck of size 24 to return to the original deck. |
|||
It takes 8 shuffles of a deck of size 52 to return to the original deck. |
|||
It takes 30 shuffles of a deck of size 100 to return to the original deck. |
|||
It takes 1018 shuffles of a deck of size 1020 to return to the original deck. |
|||
It takes 10 shuffles of a deck of size 1024 to return to the original deck. |
|||
It takes 300 shuffles of a deck of size 10000 to return to the original deck. |
|||
[1] TRUE TRUE TRUE TRUE TRUE TRUE TRUE</pre> |
|||
=={{header|Racket}}== |
|||
<syntaxhighlight lang="racket">#lang racket/base |
|||
(require racket/list) |
|||
(define (perfect-shuffle l) |
(define (perfect-shuffle l) |
||
Line 140: | Line 2,475: | ||
(foldr (λ (a b d) (list* a b d)) null as bs)) |
(foldr (λ (a b d) (list* a b d)) null as bs)) |
||
(define ( |
(define (perfect-shuffles-needed n) |
||
(define-values (_ rv) |
|||
(for/fold ((d (range n))) ((s (A002326 n))) |
|||
( |
(for/fold ((d (perfect-shuffle (range n))) (i 1)) |
||
((_ (in-naturals)) |
|||
(perfect-shuffle d))) |
|||
#:break (apply < d)) |
|||
(values (perfect-shuffle d) (add1 i)))) |
|||
rv) |
|||
(module+ test |
|||
(magic-shuffle 10) |
|||
(require rackunit) |
|||
(magic-shuffle 14) |
|||
(check-equal? (perfect-shuffle '(1 2 3 4)) '(1 3 2 4)) |
|||
(define (test-perfect-shuffles-needed n e) |
|||
(define psn (perfect-shuffles-needed n)) |
|||
(printf "Deck size:\t~a\tShuffles needed:\t~a\t(~a)~%" n psn e) |
|||
(check-equal? psn e)) |
|||
(for-each test-perfect-shuffles-needed |
|||
(define magic-numbers (for/list ((n (in-range 2 10001 2))) (A002326 n))) |
|||
'(8 24 52 100 1020 1024 10000) |
|||
'(3 11 8 30 1018 10 300)))</syntaxhighlight> |
|||
{{out}} |
|||
(append (take magic-numbers 50) (list '...) (take-right magic-numbers 50)) |
|||
<pre>Deck size: 8 Shuffles needed: 3 (3) |
|||
Deck size: 24 Shuffles needed: 11 (11) |
|||
Deck size: 52 Shuffles needed: 8 (8) |
|||
Deck size: 100 Shuffles needed: 30 (30) |
|||
Deck size: 1020 Shuffles needed: 1018 (1018) |
|||
Deck size: 1024 Shuffles needed: 10 (10) |
|||
Deck size: 10000 Shuffles needed: 300 (300)</pre> |
|||
=={{header|Raku}}== |
|||
(module+ test |
|||
(formerly Perl 6) |
|||
(require tests/eli-tester) |
|||
<syntaxhighlight lang="raku" line>for 8, 24, 52, 100, 1020, 1024, 10000 -> $size { |
|||
(test |
|||
my ($n, @deck) = 1, |^$size; |
|||
(for/list ((i (in-range 2 16 2))) (A002326 i)) => '(1 2 4 3 6 10 12) |
|||
$n++ until [<] @deck = flat [Z] @deck.rotor: @deck/2; |
|||
(perfect-shuffle '(1 2 3 4)) => '(1 3 2 4)))</lang> |
|||
printf "%5d cards: %4d\n", $size, $n; |
|||
}</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
|||
<pre>shuffle#0: deck: (0 1 2 3 4 5 6 7 8 9) |
|||
8 cards: 3 |
|||
24 cards: 11 |
|||
shuffle#2: deck: (0 7 5 3 1 8 6 4 2 9) |
|||
52 cards: 8 |
|||
shuffle#3: deck: (0 8 7 6 5 4 3 2 1 9) |
|||
100 cards: 30 |
|||
shuffle#4: deck: (0 4 8 3 7 2 6 1 5 9) |
|||
1020 cards: 1018 |
|||
shuffle#5: deck: (0 2 4 6 8 1 3 5 7 9) |
|||
1024 cards: 10 |
|||
(0 1 2 3 4 5 6 7 8 9) |
|||
10000 cards: 300 |
|||
shuffle#0: deck: (0 1 2 3 4 5 6 7 8 9 10 11 12 13) |
|||
</pre> |
|||
shuffle#1: deck: (0 7 1 8 2 9 3 10 4 11 5 12 6 13) |
|||
shuffle#2: deck: (0 10 7 4 1 11 8 5 2 12 9 6 3 13) |
|||
shuffle#3: deck: (0 5 10 2 7 12 4 9 1 6 11 3 8 13) |
|||
shuffle#4: deck: (0 9 5 1 10 6 2 11 7 3 12 8 4 13) |
|||
shuffle#5: deck: (0 11 9 7 5 3 1 12 10 8 6 4 2 13) |
|||
shuffle#6: deck: (0 12 11 10 9 8 7 6 5 4 3 2 1 13) |
|||
shuffle#7: deck: (0 6 12 5 11 4 10 3 9 2 8 1 7 13) |
|||
shuffle#8: deck: (0 3 6 9 12 2 5 8 11 1 4 7 10 13) |
|||
shuffle#9: deck: (0 8 3 11 6 1 9 4 12 7 2 10 5 13) |
|||
shuffle#10: deck: (0 4 8 12 3 7 11 2 6 10 1 5 9 13) |
|||
shuffle#11: deck: (0 2 4 6 8 10 12 1 3 5 7 9 11 13) |
|||
(0 1 2 3 4 5 6 7 8 9 10 11 12 13) |
|||
(1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 20 14 12 23 21 8 52 20 18 58 60 6 12 66 22 35 9 20 30 39 54 82 8 28 11 12 10 36 48 30 ... 9900 660 564 9906 1098 520 473 660 4830 36 3306 9922 220 174 292 3310 210 3972 522 828 9940 1620 24 588 9948 530 2412 180 3318 792 237 1620 996 4983 3322 4524 3324 180 4530 2344 3324 4884 1996 1664 4278 816 222 1332 384 300) |
|||
2 tests passed</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===unoptimized=== |
|||
<lang rexx>/*REXX pgm does a "perfect shuffle" for a number of even-numbered decks.*/ |
|||
<syntaxhighlight lang="rexx">/*REXX program performs a "perfect shuffle" for a number of even numbered decks. */ |
|||
parse arg n . /*get optional args from the C.L.*/ |
|||
parse arg X /*optional list of test cases from C.L.*/ |
|||
if X='' then X=8 24 52 100 1020 1024 10000 /*Not specified? Then use the default.*/ |
|||
w=length(n) /*W: used for formatting numbers.*/ |
|||
w=length(word(X, words(X))) /*used for right─aligning the numbers. */ |
|||
do j= |
do j=1 for words(X); y=word(X,j) /*use numbers in the test suite (list).*/ |
||
do k=1 for j; @.k=k; end /*generate the deck to be used. */ |
|||
/* [↑] keep shuffling 'til done.*/ |
|||
do t=1 until equal() /*shuffling 'til after = before.*/ |
|||
call pShuffle /*do a perfect shuffle, J items.*/ |
|||
end /*t*/ |
|||
do k=1 for y; @.k=k; end /*k*/ /*generate a deck to be used (shuffled)*/ |
|||
say 'deck size='right(j,w) " perfect shuffles="right(t,w) |
|||
do t=1 until eq(); call magic; end /*t*/ /*shuffle until before equals after.*/ |
|||
say 'deck size:' right(y,w)"," right(t,w) 'perfect shuffles.' |
|||
end /*j*/ |
end /*j*/ |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*──────────────────────────────────EQUAL subroutine────────────────────*/ |
|||
eq: do ?=1 for y; if @.?\==? then return 0; end; return 1 |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*──────────────────────────────────PSHUFFLE subroutine─────────────────*/ |
|||
magic: z=0 /*set the Z pointer (used as index).*/ |
|||
h= |
h=y%2 /*get the half─way (midpoint) pointer. */ |
||
do s=1 for h; z=z+1; h=h+1 /*traipse through the deck pips. */ |
do s=1 for h; z=z+1; h=h+1 /*traipse through the card deck pips. */ |
||
!.z=@.s; z=z+1 /*assign left half; bump pointer.*/ |
!.z=@.s; z=z+1 /*assign left half; then bump pointer. */ |
||
!.z=@.h /* " right " */ |
!.z=@.h /* " right " */ |
||
end /*s*/ /*perform perfect shuffle of deck*/ |
end /*s*/ /*perform a perfect shuffle of the deck*/ |
||
do r= |
do r=1 for y; @.r=!.r; end /*re─assign to the original card deck. */ |
||
return</ |
return</syntaxhighlight> |
||
'''output''' (abbreviated) when using the default input: |
'''output''' (abbreviated) when using the default input: |
||
<pre> |
<pre> |
||
deck size |
deck size: 8, 3 perfect shuffles. |
||
deck size |
deck size: 24, 11 perfect shuffles. |
||
deck size |
deck size: 52, 8 perfect shuffles. |
||
deck size |
deck size: 100, 30 perfect shuffles. |
||
deck size |
deck size: 1020, 1018 perfect shuffles. |
||
deck size |
deck size: 1024, 10 perfect shuffles. |
||
deck size |
deck size: 10000, 300 perfect shuffles. |
||
deck size=16 perfect shuffles= 4 |
|||
deck size=18 perfect shuffles= 8 |
|||
deck size=20 perfect shuffles=18 |
|||
deck size=22 perfect shuffles= 6 |
|||
deck size=24 perfect shuffles=11 |
|||
deck size=26 perfect shuffles=20 |
|||
deck size=28 perfect shuffles=18 |
|||
deck size=30 perfect shuffles=28 |
|||
deck size=32 perfect shuffles= 5 |
|||
deck size=34 perfect shuffles=10 |
|||
deck size=36 perfect shuffles=12 |
|||
deck size=38 perfect shuffles=36 |
|||
deck size=40 perfect shuffles=12 |
|||
∙ |
|||
∙ |
|||
∙ |
|||
(elided) |
|||
</pre> |
</pre> |
||
===optimized=== |
|||
This REXX version takes advantage that the 1<sup>st</sup> and last cards of the deck don't change. |
|||
<syntaxhighlight lang="rexx">/*REXX program does a "perfect shuffle" for a number of even numbered decks. */ |
|||
parse arg X /*optional list of test cases from C.L.*/ |
|||
if X='' then X=8 24 52 100 1020 1024 10000 /*Not specified? Use default.*/ |
|||
w=length(word(X, words(X))) /*used for right─aligning the numbers. */ |
|||
do j=1 for words(X); y=word(X,j) /*use numbers in the test suite (list).*/ |
|||
do k=1 for y; @.k=k; end /*generate a deck to be shuffled (used)*/ |
|||
do t=1 until eq(); call magic; end /*shuffle until before equals after.*/ |
|||
say 'deck size:' right(y,w)"," right(t,w) 'perfect shuffles.' |
|||
end /*j*/ |
|||
exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
eq: do ?=1 for y; if @.?\==? then return 0; end; return 1 |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
magic: z=1; h=y%2 /*H is (half─way) pointer.*/ |
|||
do L=3 by 2 for h-1; z=z+1; !.L=@.z; end /*assign left half of deck.*/ |
|||
do R=2 by 2 for h-1; h=h+1; !.R=@.h; end /* " right " " " */ |
|||
do a=2 for y-2; @.a=!.a; end /*re─assign──►original deck*/ |
|||
return</syntaxhighlight> |
|||
'''output''' is the same as the 1<sup>st</sup> version. |
|||
<br><br> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<lang ruby>def perfect_shuffle(n) |
|||
<syntaxhighlight lang="ruby">def perfect_shuffle(deck_size = 52) |
|||
start = *1..n |
|||
deck = |
deck = (1..deck_size).to_a |
||
original = deck.dup |
|||
half = deck_size / 2 |
|||
magic_shuffle = ->(d){ d.shift(m).zip(d).flatten } |
|||
1.step do |i| |
1.step do |i| |
||
deck = |
deck = deck.first(half).zip(deck.last(half)).flatten |
||
return i if deck == |
return i if deck == original |
||
end |
end |
||
end |
end |
||
[8, 24, 52, 100, 1020, 1024, 10000].each {|i| puts "Perfect shuffles required for deck size #{i}: #{perfect_shuffle(i)}"} |
|||
fmt = "%4d -%5d :" + "%5d" * 20 |
|||
</syntaxhighlight> |
|||
(2..10000).step(2).each_slice(20) do |ary| |
|||
puts fmt % [*ary.minmax, *ary.map{|n| perfect_shuffle(n)}] |
|||
{{out}} |
|||
end</lang> |
|||
<pre> |
|||
Perfect shuffles required for deck size 8: 3 |
|||
Perfect shuffles required for deck size 24: 11 |
|||
Perfect shuffles required for deck size 52: 8 |
|||
Perfect shuffles required for deck size 100: 30 |
|||
Perfect shuffles required for deck size 1020: 1018 |
|||
Perfect shuffles required for deck size 1024: 10 |
|||
Perfect shuffles required for deck size 10000: 300 |
|||
</pre> |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust">extern crate itertools; |
|||
fn shuffle<T>(mut deck: Vec<T>) -> Vec<T> { |
|||
let index = deck.len() / 2; |
|||
let right_half = deck.split_off(index); |
|||
itertools::interleave(deck, right_half).collect() |
|||
} |
|||
fn main() { |
|||
for &size in &[8, 24, 52, 100, 1020, 1024, 10_000] { |
|||
let original_deck: Vec<_> = (0..size).collect(); |
|||
let mut deck = original_deck.clone(); |
|||
let mut iterations = 0; |
|||
loop { |
|||
deck = shuffle(deck); |
|||
iterations += 1; |
|||
if deck == original_deck { |
|||
break; |
|||
} |
|||
} |
|||
println!("{: >5}: {: >4}", size, iterations); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 8: 3 |
|||
24: 11 |
|||
52: 8 |
|||
100: 30 |
|||
1020: 1018 |
|||
1024: 10 |
|||
10000: 300 |
|||
</pre> |
|||
=={{header|Scala}}== |
|||
===Imperative, Quick, dirty and ugly=== |
|||
{{trans|Java}} |
|||
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/Ux9RKDx/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/eWeiDIBbQMGpNIQAmvXfLg Scastie (remote JVM)]. |
|||
<syntaxhighlight lang="scala">object PerfectShuffle extends App { |
|||
private def sizes = Seq(8, 24, 52, 100, 1020, 1024, 10000) |
|||
private def perfectShuffle(size: Int): Int = { |
|||
require(size % 2 == 0, "Card deck must be even") |
|||
val (half, a) = (size / 2, Array.range(0, size)) |
|||
val original = a.clone |
|||
var count = 1 |
|||
while (true) { |
|||
val aa = a.clone |
|||
for (i <- 0 until half) { |
|||
a(2 * i) = aa(i) |
|||
a(2 * i + 1) = aa(i + half) |
|||
} |
|||
if (a.deep == original.deep) return count |
|||
count += 1 |
|||
} |
|||
0 |
|||
} |
|||
for (size <- sizes) println(f"$size%5d : ${perfectShuffle(size)}%5d") |
|||
}</syntaxhighlight> |
|||
=={{header|Scilab}}== |
|||
{{trans|MATLAB}} |
|||
<syntaxhighlight lang="text">function New=PerfectShuffle(Nitems,Nturns) |
|||
if modulo(Nitems,2)==0 then |
|||
X=1:Nitems; |
|||
for c=1:Nturns |
|||
X=matrix(X,Nitems/2,2)'; |
|||
X=X(:); |
|||
end |
|||
New=X'; |
|||
end |
|||
endfunction |
|||
Result=[]; |
|||
Q=[8, 24, 52, 100, 1020, 1024, 10000]; |
|||
for n=Q |
|||
Same=0; |
|||
T=0; |
|||
Compare=[]; |
|||
while ~Same |
|||
T=T+1; |
|||
R=PerfectShuffle(n,T); |
|||
Compare = find(R-(1:n)); |
|||
if Compare == [] then |
|||
Same = 1; |
|||
end |
|||
end |
|||
Result=[Result;T]; |
|||
end |
|||
disp([Q', Result])</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 8. 3. |
|||
24. 11. |
|||
52. 8. |
|||
100. 30. |
|||
1020. 1018. |
|||
1024. 10. |
|||
10000. 300.</pre> |
|||
=={{header|SETL}}== |
|||
<syntaxhighlight lang="setl">program faro_shuffle; |
|||
loop for test in [8, 24, 52, 100, 1020, 1024, 10000] do |
|||
print(lpad(str test, 5) + " cards: " + lpad(str cycle [1..test], 4)); |
|||
end loop; |
|||
op cycle(l); |
|||
start := l; |
|||
loop until l = start do |
|||
l := shuffle l; |
|||
n +:= 1; |
|||
end loop; |
|||
return n; |
|||
end op; |
|||
op shuffle(l); |
|||
return [l(mapindex(i,#l)) : i in [1..#l]]; |
|||
end op; |
|||
proc mapindex(i, size); |
|||
return if odd i then i div 2+1 else (i+size) div 2 end; |
|||
end proc; |
|||
end program;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 8 cards: 3 |
|||
24 cards: 11 |
|||
52 cards: 8 |
|||
100 cards: 30 |
|||
1020 cards: 1018 |
|||
1024 cards: 10 |
|||
10000 cards: 300</pre> |
|||
=={{header|Sidef}}== |
|||
{{trans|Perl}} |
|||
<syntaxhighlight lang="ruby">func perfect_shuffle(deck) { |
|||
deck/2 -> zip.flat |
|||
} |
|||
[8, 24, 52, 100, 1020, 1024, 10000].each { |size| |
|||
var deck = @(1..size) |
|||
var shuffled = deck |
|||
var n = (1..Inf -> lazy.first { |
|||
(shuffled = perfect_shuffle(shuffled)) == deck |
|||
}) |
|||
printf("%5d cards: %4d\n", size, n) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8 cards: 3 |
|||
24 cards: 11 |
|||
52 cards: 8 |
|||
100 cards: 30 |
|||
1020 cards: 1018 |
|||
1024 cards: 10 |
|||
10000 cards: 300 |
|||
</pre> |
|||
=={{header|Swift}}== |
|||
<syntaxhighlight lang="swift">func perfectShuffle<T>(_ arr: [T]) -> [T]? { |
|||
guard arr.count & 1 == 0 else { |
|||
return nil |
|||
} |
|||
let half = arr.count / 2 |
|||
var res = [T]() |
|||
for i in 0..<half { |
|||
res.append(arr[i]) |
|||
res.append(arr[i + half]) |
|||
} |
|||
return res |
|||
} |
|||
let decks = [ |
|||
Array(1...8), |
|||
Array(1...24), |
|||
Array(1...52), |
|||
Array(1...100), |
|||
Array(1...1020), |
|||
Array(1...1024), |
|||
Array(1...10000) |
|||
] |
|||
for deck in decks { |
|||
var shuffled = deck |
|||
var shuffles = 0 |
|||
repeat { |
|||
shuffled = perfectShuffle(shuffled)! |
|||
shuffles += 1 |
|||
} while shuffled != deck |
|||
print("Deck of \(shuffled.count) took \(shuffles) shuffles to get back to original order") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Deck of 8 took 3 shuffles to get back to original order |
|||
Deck of 24 took 11 shuffles to get back to original order |
|||
Deck of 52 took 8 shuffles to get back to original order |
|||
Deck of 100 took 30 shuffles to get back to original order |
|||
Deck of 1020 took 1018 shuffles to get back to original order |
|||
Deck of 1024 took 10 shuffles to get back to original order |
|||
Deck of 10000 took 300 shuffles to get back to original order</pre> |
|||
=={{header|Tcl}}== |
|||
Using <tt>tcltest</tt> to include an executable test case .. |
|||
<syntaxhighlight lang="tcl">namespace eval shuffle { |
|||
proc perfect {deck} { |
|||
if {[llength $deck]%2} { |
|||
return -code error "Deck must be of even length!" |
|||
} |
|||
set split [expr {[llength $deck]/2}] |
|||
set top [lrange $deck 0 $split-1] |
|||
set btm [lrange $deck $split end] |
|||
foreach a $top b $btm { |
|||
lappend res $a $b |
|||
} |
|||
return $res |
|||
} |
|||
proc cycle_length {transform deck} { |
|||
set d $deck |
|||
while 1 { |
|||
set d [$transform $d] |
|||
incr i |
|||
if {$d eq $deck} {return $i} |
|||
} |
|||
return $i |
|||
} |
|||
proc range {a {b ""}} { |
|||
if {$b eq ""} { |
|||
set b $a; set a 0 |
|||
} |
|||
set res {} |
|||
while {$a < $b} { |
|||
lappend res $a |
|||
incr a |
|||
} |
|||
return $res |
|||
} |
|||
} |
|||
set ::argv {} |
|||
package require tcltest |
|||
tcltest::test "Test perfect shuffle cycles" {} -body { |
|||
lmap size {8 24 52 100 1020 1024 10000} { |
|||
shuffle::cycle_length perfect [range $size] |
|||
} |
|||
} -result {3 11 8 30 1018 10 300}</syntaxhighlight> |
|||
=={{header|UNIX Shell}}== |
|||
{{works with|Bourne Again SHell}} |
|||
{{works with|Korn Shell}} |
|||
{{works with|Zsh}} |
|||
<syntaxhighlight lang="bash">function faro { |
|||
if (( $# % 2 )); then |
|||
printf >&2 'Can only shuffle an even number of elements!\n' |
|||
return 1 |
|||
fi |
|||
typeset -i half=$(($#/2)) i |
|||
typeset argv=("$@") |
|||
for (( i=0; i<half; ++i )); do |
|||
printf '%s\n%s\n' "${argv[i${ZSH_VERSION:++1}]}" "${argv[i+half${ZSH_VERSION:++1}]}" |
|||
done |
|||
} |
|||
function count_faros { |
|||
typeset argv=("$@") |
|||
typeset -i count=0 |
|||
argv=($(faro "${argv[@]}")) |
|||
(( count += 1 )) |
|||
while [[ "${argv[*]}" != "$*" ]]; do |
|||
argv=($(faro "${argv[@]}")) |
|||
(( count += 1 )) |
|||
done |
|||
printf '%d\n' "$count" |
|||
} |
|||
# Include time taken, which is combined from the three shells in the output below |
|||
printf '%s\t%s\t%s\n' Size Shuffles Seconds |
|||
for size in 8 24 52 100 1020 1024 10000; do |
|||
eval "array=({1..$size})" |
|||
start=$(date +%s) |
|||
count=$(count_faros "${array[@]}") |
|||
taken=$(( $(date +%s) - start )) |
|||
printf '%d\t%d\t%d\n' "$size" "$count" "$taken" |
|||
done |
|||
</syntaxhighlight> |
|||
{{Out}} |
|||
<pre> |
|||
Size Shuffles Seconds (Bash/Ksh/Zsh) |
|||
8 3 0/0/0 |
|||
24 11 0/0/0 |
|||
52 8 0/0/0 |
|||
100 30 0/0/0 |
|||
1020 1018 20/4/8 |
|||
1024 10 0/0/0 |
|||
10000 300 87/12/29</pre> |
|||
=={{header|VBA}}== |
|||
<syntaxhighlight lang="vb">Option Explicit |
|||
Sub Main() |
|||
Dim T, Arr, X As Long, C As Long |
|||
Arr = Array(8, 24, 52, 100, 1020, 1024, 10000) |
|||
For X = LBound(Arr) To UBound(Arr) |
|||
C = 0 |
|||
Call PerfectShuffle(T, CLng(Arr(X)), C) |
|||
Debug.Print Right(String(19, " ") & "For " & Arr(X) & " cards => ", 19) & C & " shuffles needed." |
|||
Erase T |
|||
Next |
|||
End Sub |
|||
Private Sub PerfectShuffle(tb, NbCards As Long, Count As Long) |
|||
Dim arr1, arr2, StrInit As String, StrTest As String |
|||
tb = CreateArray(1, NbCards) |
|||
StrInit = Join(tb, " ") |
|||
Do |
|||
Count = Count + 1 |
|||
Call DivideArr(tb, arr1, arr2) |
|||
tb = RemakeArray(arr1, arr2) |
|||
StrTest = Join(tb, " ") |
|||
Loop While StrTest <> StrInit |
|||
End Sub |
|||
Private Function CreateArray(First As Long, Length As Long) As String() |
|||
Dim i As Long, T() As String, C As Long |
|||
If IsEven(Length) Then |
|||
ReDim T(Length - 1) |
|||
For i = First To First + Length - 1 |
|||
T(C) = i |
|||
C = C + 1 |
|||
Next i |
|||
CreateArray = T |
|||
End If |
|||
End Function |
|||
Private Sub DivideArr(A, B, C) |
|||
Dim i As Long |
|||
B = A |
|||
ReDim Preserve B(UBound(A) \ 2) |
|||
ReDim C(UBound(B)) |
|||
For i = LBound(C) To UBound(C) |
|||
C(i) = A(i + UBound(B) + 1) |
|||
Next |
|||
End Sub |
|||
Private Function RemakeArray(A1, A2) As String() |
|||
Dim i As Long, T() As String, C As Long |
|||
ReDim T((UBound(A2) * 2) + 1) |
|||
For i = LBound(T) To UBound(T) - 1 Step 2 |
|||
T(i) = A1(C) |
|||
T(i + 1) = A2(C) |
|||
C = C + 1 |
|||
Next |
|||
RemakeArray = T |
|||
End Function |
|||
Private Function IsEven(Number As Long) As Boolean |
|||
IsEven = (Number Mod 2 = 0) |
|||
End Function</syntaxhighlight> |
|||
{{out}} |
|||
<pre> For 8 cards => 3 shuffles needed. |
|||
For 24 cards => 11 shuffles needed. |
|||
For 52 cards => 8 shuffles needed. |
|||
For 100 cards => 30 shuffles needed. |
|||
For 1020 cards => 1018 shuffles needed. |
|||
For 1024 cards => 10 shuffles needed. |
|||
For 10000 cards => 300 shuffles needed.</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Kotlin}} |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
|||
var areSame = Fn.new { |a, b| |
|||
for (i in 0...a.count) if (a[i] != b[i]) return false |
|||
return true |
|||
} |
|||
var perfectShuffle = Fn.new { |a| |
|||
var n = a.count |
|||
var b = List.filled(n, 0) |
|||
var hSize = (n/2).floor |
|||
for (i in 0...hSize) b[i * 2] = a[i] |
|||
var j = 1 |
|||
for (i in hSize...n) { |
|||
b[j] = a[i] |
|||
j = j + 2 |
|||
} |
|||
return b |
|||
} |
|||
var countShuffles = Fn.new { |a| |
|||
var n = a.count |
|||
if (n < 2 || n % 2 == 1) Fiber.abort("Array must be even-sized and non-empty.") |
|||
var b = a |
|||
var count = 0 |
|||
while (true) { |
|||
var c = perfectShuffle.call(b) |
|||
count = count + 1 |
|||
if (areSame.call(a, c)) return count |
|||
b = c |
|||
} |
|||
} |
|||
System.print("Deck size Num shuffles") |
|||
System.print("--------- ------------") |
|||
var sizes = [8, 24, 52, 100, 1020, 1024, 10000] |
|||
for (size in sizes) { |
|||
var a = List.filled(size, 0) |
|||
for (i in 1...size) a[i] = i |
|||
var count = countShuffles.call(a) |
|||
Fmt.print("$-9d $d", size, count) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Deck size Num shuffles |
|||
--------- ------------ |
|||
8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300 |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight lang="xpl0">int Deck(10000), Deck0(10000); |
|||
int Cases, Count, Test, Size, I; |
|||
proc Shuffle; \Do perfect shuffle of Deck0 into Deck |
|||
int DeckLeft, DeckRight; |
|||
int I; |
|||
[DeckLeft:= Deck0; |
|||
DeckRight:= Deck0 + Size*4/2; \4 bytes per integer |
|||
for I:= 0 to Size-1 do |
|||
Deck(I):= if I&1 then DeckRight(I/2) |
|||
else DeckLeft(I/2); |
|||
]; |
|||
[Cases:= [8, 24, 52, 100, 1020, 1024, 10000]; |
|||
for Test:= 0 to 7-1 do |
|||
[Size:= Cases(Test); |
|||
for I:= 0 to Size-1 do Deck(I):= I; |
|||
Count:= 0; |
|||
repeat for I:= 0 to Size-1 do Deck0(I):= Deck(I); |
|||
Shuffle; |
|||
Count:= Count+1; |
|||
for I:= 0 to Size-1 do |
|||
if Deck(I) # I then I:= Size; |
|||
until I = Size; \equal starting configuration |
|||
IntOut(0, Size); ChOut(0, 9\tab\); IntOut(0, Count); CrLf(0); |
|||
]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
8 3 |
|||
24 11 |
|||
52 8 |
|||
100 30 |
|||
1020 1018 |
|||
1024 10 |
|||
10000 300 |
|||
</pre> |
|||
=={{header|zkl}}== |
|||
<syntaxhighlight lang="zkl">fcn perfectShuffle(numCards){ |
|||
deck,shuffle,n,N:=numCards.pump(List),deck,0,numCards/2; |
|||
do{ shuffle=shuffle[0,N].zip(shuffle[N,*]).flatten(); n+=1 } |
|||
while(deck!=shuffle); |
|||
n |
|||
} |
|||
foreach n in (T(8,24,52,100,1020,1024,10000)){ |
|||
println("%5d : %d".fmt(n,perfectShuffle(n))); |
|||
}</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
8 : 3 |
|||
2 - 40 : 1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 |
|||
24 : 11 |
|||
42 - 80 : 20 14 12 23 21 8 52 20 18 58 60 6 12 66 22 35 9 20 30 39 |
|||
52 : 8 |
|||
82 - 120 : 54 82 8 28 11 12 10 36 48 30 100 51 12 106 36 36 28 44 12 24 |
|||
100 : 30 |
|||
122 - 160 : 110 20 100 7 14 130 18 36 68 138 46 60 28 42 148 15 24 20 52 52 |
|||
1020 : 1018 |
|||
162 - 200 : 33 162 20 83 156 18 172 60 58 178 180 60 36 40 18 95 96 12 196 99 |
|||
1024 : 10 |
|||
202 - 240 : 66 84 20 66 90 210 70 28 15 18 24 37 60 226 76 30 29 92 78 119 |
|||
10000 : 300 |
|||
242 - 280 : 24 162 84 36 82 50 110 8 16 36 84 131 52 22 268 135 12 20 92 30 |
|||
282 - 320 : 70 94 36 60 136 48 292 116 90 132 42 100 60 102 102 155 156 12 316 140 |
|||
322 - 360 : 106 72 60 36 69 30 36 132 21 28 10 147 44 346 348 36 88 140 24 179 |
|||
362 - 400 : 342 110 36 183 60 156 372 100 84 378 14 191 60 42 388 88 130 156 44 18 |
|||
402 - 440 : 200 60 108 180 204 68 174 164 138 418 420 138 40 60 60 43 72 28 198 73 |
|||
442 - 480 : 42 442 44 148 224 20 30 12 76 72 460 231 20 466 66 52 70 180 156 239 |
|||
482 - 520 : 36 66 48 243 162 490 56 60 105 166 166 251 100 156 508 9 18 204 230 172 |
|||
522 - 560 : 260 522 60 40 253 174 60 212 178 210 540 180 36 546 60 252 39 36 556 84 |
|||
562 - 600 : 40 562 28 54 284 114 190 220 144 96 246 260 12 586 90 196 148 24 198 299 |
|||
. |
|||
. |
|||
. |
|||
9602 - 9640 : 2400 240 56 492 3202 4116 9612 64 4698 9618 1068 283 300 1604 9628 1605 468 460 418 216 |
|||
9642 - 9680 : 155 9642 428 4380 402 804 588 3860 252 4452 9660 644 644 1380 1460 4572 568 420 9676 4839 |
|||
9682 - 9720 : 1380 4620 444 1076 4844 110 3222 276 2424 780 396 780 1292 456 18 492 4410 924 780 43 |
|||
9722 - 9760 : 810 462 1940 2380 1518 4716 9732 580 636 3246 760 4871 1948 342 9748 693 650 3900 4430 3252 |
|||
9762 - 9800 : 1582 1500 60 4883 1221 814 84 440 1086 210 652 1086 612 3262 300 4895 699 652 1200 2380 |
|||
9802 - 9840 : 2970 9802 468 1398 144 3270 1090 60 1636 3270 660 2070 260 1580 1404 28 4916 420 1092 4919 |
|||
9842 - 9880 : 756 96 1780 532 462 9850 4814 36 4928 9858 1548 2112 1972 660 4830 4935 822 3900 984 396 |
|||
9882 - 9920 : 120 9882 1316 4943 140 156 1140 3956 3298 2340 9900 660 564 9906 1098 520 473 660 4830 36 |
|||
9922 - 9960 : 3306 9922 220 174 292 3310 210 3972 522 828 9940 1620 24 588 9948 530 2412 180 3318 792 |
|||
9962 -10000 : 237 1620 996 4983 3322 4524 3324 180 4530 2344 3324 4884 1996 1664 4278 816 222 1332 384 300 |
|||
</pre> |
</pre> |
Latest revision as of 12:16, 24 January 2024
You are encouraged to solve this task according to the task description, using any language you may know.
A perfect shuffle (or faro/weave shuffle) means splitting a deck of cards into equal halves, and perfectly interleaving them - so that you end up with the first card from the left half, followed by the first card from the right half, and so on:
- 7♠ 8♠ 9♠ J♠ Q♠ K♠→7♠ 8♠ 9♠
J♠ Q♠ K♠→7♠ J♠ 8♠ Q♠ 9♠ K♠
When you repeatedly perform perfect shuffles on an even-sized deck of unique cards, it will at some point arrive back at its original order. How many shuffles this takes, depends solely on the number of cards in the deck - for example for a deck of eight cards it takes three shuffles:
original: 1 2 3 4 5 6 7 8
after 1st shuffle: 1 5 2 6 3 7 4 8
after 2nd shuffle: 1 3 5 7 2 4 6 8
after 3rd shuffle: 1 2 3 4 5 6 7 8
The Task
- Write a function that can perform a perfect shuffle on an even-sized list of values.
- Call this function repeatedly to count how many shuffles are needed to get a deck back to its original order, for each of the deck sizes listed under "Test Cases" below.
- You can use a list of numbers (or anything else that's convenient) to represent a deck; just make sure that all "cards" are unique within each deck.
- Print out the resulting shuffle counts, to demonstrate that your program passes the test-cases.
Test Cases
input (deck size) output (number of shuffles required) 8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
11l
F flatten(lst)
[Int] r
L(sublst) lst
L(i) sublst
r [+]= i
R r
F magic_shuffle(deck)
V half = deck.len I/ 2
R flatten(zip(deck[0 .< half], deck[half ..]))
F after_how_many_is_equal(start, end)
V deck = magic_shuffle(start)
V counter = 1
L deck != end
deck = magic_shuffle(deck)
counter++
R counter
print(‘Length of the deck of cards | Perfect shuffles needed to obtain the same deck back’)
L(length) (8, 24, 52, 100, 1020, 1024, 10000)
V deck = Array(0 .< length)
V shuffles_needed = after_how_many_is_equal(deck, deck)
print(‘#<5 | #.’.format(length, shuffles_needed))
- Output:
Length of the deck of cards | Perfect shuffles needed to obtain the same deck back 8 | 3 24 | 11 52 | 8 100 | 30 1020 | 1018 1024 | 10 10000 | 300
Action!
Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU.
DEFINE MAXDECK="5000"
PROC Order(INT ARRAY deck INT count)
INT i
FOR i=0 TO count-1
DO
deck(i)=i
OD
RETURN
BYTE FUNC IsOrdered(INT ARRAY deck INT count)
INT i
FOR i=0 TO count-1
DO
IF deck(i)#i THEN
RETURN (0)
FI
OD
RETURN (1)
PROC Shuffle(INT ARRAY src,dst INT count)
INT i,i1,i2
i=0 i1=0 i2=count RSH 1
WHILE i<count
DO
dst(i)=src(i1) i==+1 i1==+1
dst(i)=src(i2) i==+1 i2==+1
OD
RETURN
PROC Test(INT ARRAY deck,deck2 INT count)
INT ARRAY tmp
INT n
Order(deck,count)
n=0
DO
Shuffle(deck,deck2,count)
tmp=deck deck=deck2 deck2=tmp
n==+1
Poke(77,0) ;turn off the attract mode
PrintF("%I cards -> %I iterations%E",count,n)
Put(28) ;move cursor up
UNTIL IsOrdered(deck,count)
OD
PutE()
RETURN
PROC Main()
INT ARRAY deck(MAXDECK),deck2(MAXDECK)
INT ARRAY counts=[8 24 52 100 1020 1024 MAXDECK]
INT i
FOR i=0 TO 6
DO
Test(deck,deck2,counts(i))
OD
RETURN
- Output:
Screenshot from Atari 8-bit computer
8 cards -> 3 iterations 24 cards -> 11 iterations 52 cards -> 8 iterations 100 cards -> 30 iterations 1020 cards -> 1018 iterations 1024 cards -> 10 iterations 5000 cards -> 357 iterations
Ada
with ada.text_io;use ada.text_io;
procedure perfect_shuffle is
function count_shuffle (half_size : Positive) return Positive is
subtype index is Natural range 0..2 * half_size - 1;
subtype index_that_move is index range index'first+1..index'last-1;
type deck is array (index) of index;
initial, d, next : deck;
count : Natural := 1;
begin
for i in index loop initial (i) := i; end loop;
d := initial;
loop
for i in index_that_move loop
next (i) := (if d (i) mod 2 = 0 then d(i)/2 else d(i)/2 + half_size);
end loop;
exit when next (index_that_move)= initial(index_that_move);
d := next;
count := count + 1;
end loop;
return count;
end count_shuffle;
test : array (Positive range <>) of Positive := (8, 24, 52, 100, 1020, 1024, 10_000);
begin
for size of test loop
put_line ("For" & size'img & " cards, there are "& count_shuffle (size / 2)'img & " shuffles needed.");
end loop;
end perfect_shuffle;
- Output:
For 8 cards, there are 3 shuffles needed. For 24 cards, there are 11 shuffles needed. For 52 cards, there are 8 shuffles needed. For 100 cards, there are 30 shuffles needed. For 1020 cards, there are 1018 shuffles needed. For 1024 cards, there are 10 shuffles needed. For 10000 cards, there are 300 shuffles needed.
ALGOL 68
# returns an array of the specified length, initialised to an ascending sequence of integers #
OP DECK = ( INT length )[]INT:
BEGIN
[ 1 : length ]INT result;
FOR i TO UPB result DO result[ i ] := i OD;
result
END # DECK # ;
# in-place shuffles the deck as per the task requirements #
# LWB deck is assumed to be 1 #
PROC shuffle = ( REF[]INT deck )VOID:
BEGIN
[ 1 : UPB deck ]INT result;
INT left pos := 1;
INT right pos := ( UPB deck OVER 2 ) + 1;
FOR i FROM 2 BY 2 TO UPB result DO
result[ left pos ] := deck[ i - 1 ];
result[ right pos ] := deck[ i ];
left pos +:= 1;
right pos +:= 1
OD;
FOR i TO UPB deck DO deck[ i ] := result[ i ] OD
END # SHUFFLE # ;
# compares two integer arrays for equality #
OP = = ( []INT a, b )BOOL:
IF LWB a /= LWB b OR UPB a /= UPB b
THEN # the arrays have different bounds #
FALSE
ELSE
BOOL result := TRUE;
FOR i FROM LWB a TO UPB a WHILE result := a[ i ] = b[ i ] DO SKIP OD;
result
FI # = # ;
# compares two integer arrays for inequality #
OP /= = ( []INT a, b )BOOL: NOT ( a = b );
# returns the number of shuffles required to return a deck of the specified length #
# back to its original state #
PROC count shuffles = ( INT length )INT:
BEGIN
[] INT original deck = DECK length;
[ 1 : length ]INT shuffled deck := original deck;
INT count := 1;
WHILE shuffle( shuffled deck );
shuffled deck /= original deck
DO
count +:= 1
OD;
count
END # count shuffles # ;
# test the shuffling #
[]INT lengths = ( 8, 24, 52, 100, 1020, 1024, 10 000 );
FOR l FROM LWB lengths TO UPB lengths DO
print( ( whole( lengths[ l ], -8 ) + ": " + whole( count shuffles( lengths[ l ] ), -6 ), newline ) )
OD
- Output:
8: 3 24: 11 52: 8 100: 30 1020: 1018 1024: 10 10000: 300
APL
faro ← ∊∘⍉(2,2÷⍨≢)⍴⊢
count ← {⍺←⍵ ⋄ ⍺≡r←⍺⍺ ⍵:1 ⋄ 1+⍺∇r}
(⊢,[1.5] (faro count ⍳)¨) 8 24 52 100 1020 1024 10000
- Output:
8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
Arturo
perfectShuffle: function [deckSize][
deck: 1..deckSize
original: new deck
halfDeck: deckSize/2
i: 1
while [true][
deck: flatten couple first.n: halfDeck deck last.n: halfDeck deck
if deck = original -> return i
i: i+1
]
]
loop [8 24 52 100 1020 1024 10000] 's ->
print [
pad.right join @["Perfect shuffles required for deck size " to :string s ":"] 48
perfectShuffle s
]
- Output:
Perfect shuffles required for deck size 8: 3 Perfect shuffles required for deck size 24: 11 Perfect shuffles required for deck size 52: 8 Perfect shuffles required for deck size 100: 30 Perfect shuffles required for deck size 1020: 1018 Perfect shuffles required for deck size 1024: 10 Perfect shuffles required for deck size 10000: 300
AutoHotkey
Shuffle(cards){
n := cards.MaxIndex()/2, res := []
loop % n
res.push(cards[A_Index]), res.push(cards[round(A_Index + n)])
return res
}
Examples:
test := [8, 24, 52, 100, 1020, 1024, 10000]
for each, val in test
{
cards := [], original:=rep:=""
loop, % val
cards.push(A_Index), original .= (original?", ":"") A_Index
while (res <> original)
{
res := ""
for k, v in (cards := Shuffle(cards))
res .= (res?", ":"") v
rep := A_Index
}
result .= val "`t" rep "`n"
}
MsgBox % result
return
Outputs:
8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
C
/* ===> INCLUDES <============================================================*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/* ===> CONSTANTS <===========================================================*/
#define N_DECKS 7
const int kDecks[N_DECKS] = { 8, 24, 52, 100, 1020, 1024, 10000 };
/* ===> FUNCTION PROTOTYPES <=================================================*/
int CreateDeck( int **deck, int nCards );
void InitDeck( int *deck, int nCards );
int DuplicateDeck( int **dest, const int *orig, int nCards );
int InitedDeck( int *deck, int nCards );
int ShuffleDeck( int *deck, int nCards );
void FreeDeck( int **deck );
/* ===> FUNCTION DEFINITIONS <================================================*/
int main() {
int i, nCards, nShuffles;
int *deck = NULL;
for( i=0; i<N_DECKS; ++i ) {
nCards = kDecks[i];
if( !CreateDeck(&deck,nCards) ) {
fprintf( stderr, "Error: malloc() failed!\n" );
return 1;
}
InitDeck( deck, nCards );
nShuffles = 0;
do {
ShuffleDeck( deck, nCards );
++nShuffles;
} while( !InitedDeck(deck,nCards) );
printf( "Cards count: %d, shuffles required: %d.\n", nCards, nShuffles );
FreeDeck( &deck );
}
return 0;
}
int CreateDeck( int **deck, int nCards ) {
int *tmp = NULL;
if( deck != NULL )
tmp = malloc( nCards*sizeof(*tmp) );
return tmp!=NULL ? (*deck=tmp)!=NULL : 0; /* (?success) (:failure) */
}
void InitDeck( int *deck, int nCards ) {
if( deck != NULL ) {
int i;
for( i=0; i<nCards; ++i )
deck[i] = i;
}
}
int DuplicateDeck( int **dest, const int *orig, int nCards ) {
if( orig != NULL && CreateDeck(dest,nCards) ) {
memcpy( *dest, orig, nCards*sizeof(*orig) );
return 1; /* success */
}
else {
return 0; /* failure */
}
}
int InitedDeck( int *deck, int nCards ) {
int i;
for( i=0; i<nCards; ++i )
if( deck[i] != i )
return 0; /* not inited */
return 1; /* inited */
}
int ShuffleDeck( int *deck, int nCards ) {
int *copy = NULL;
if( DuplicateDeck(©,deck,nCards) ) {
int i, j;
for( i=j=0; i<nCards/2; ++i, j+=2 ) {
deck[j] = copy[i];
deck[j+1] = copy[i+nCards/2];
}
FreeDeck( © );
return 1; /* success */
}
else {
return 0; /* failure */
}
}
void FreeDeck( int **deck ) {
if( *deck != NULL ) {
free( *deck );
*deck = NULL;
}
}
- Output:
Cards count: 8, shuffles required: 3. Cards count: 24, shuffles required: 11. Cards count: 52, shuffles required: 8. Cards count: 100, shuffles required: 30. Cards count: 1020, shuffles required: 1018. Cards count: 1024, shuffles required: 10. Cards count: 10000, shuffles required: 300. Press "Enter" to quit...
C#
using System;
using System.Collections.Generic;
using System.Linq;
public static class PerfectShuffle
{
static void Main()
{
foreach (int input in new [] {8, 24, 52, 100, 1020, 1024, 10000}) {
int[] numbers = Enumerable.Range(1, input).ToArray();
Console.WriteLine($"{input} cards: {ShuffleThrough(numbers).Count()}");
}
IEnumerable<T[]> ShuffleThrough<T>(T[] original) {
T[] copy = (T[])original.Clone();
do {
yield return copy = Shuffle(copy);
} while (!Enumerable.SequenceEqual(original, copy));
}
}
public static T[] Shuffle<T>(T[] array) {
if (array.Length % 2 != 0) throw new ArgumentException("Length must be even.");
int half = array.Length / 2;
T[] result = new T[array.Length];
for (int t = 0, l = 0, r = half; l < half; t+=2, l++, r++) {
result[t] = array[l];
result[t+1] = array[r];
}
return result;
}
}
- Output:
8 cards: 3 24 cards: 11 52 cards: 8 100 cards: 30 1020 cards: 1018 1024 cards: 10 10000 cards: 300
C++
#include <iostream>
#include <algorithm>
#include <vector>
int pShuffle( int t ) {
std::vector<int> v, o, r;
for( int x = 0; x < t; x++ ) {
o.push_back( x + 1 );
}
r = o;
int t2 = t / 2 - 1, c = 1;
while( true ) {
v = r;
r.clear();
for( int x = t2; x > -1; x-- ) {
r.push_back( v[x + t2 + 1] );
r.push_back( v[x] );
}
std::reverse( r.begin(), r.end() );
if( std::equal( o.begin(), o.end(), r.begin() ) ) return c;
c++;
}
}
int main() {
int s[] = { 8, 24, 52, 100, 1020, 1024, 10000 };
for( int x = 0; x < 7; x++ ) {
std::cout << "Cards count: " << s[x] << ", shuffles required: ";
std::cout << pShuffle( s[x] ) << ".\n";
}
return 0;
}
- Output:
Cards count: 8, shuffles required: 3. Cards count: 24, shuffles required: 11. Cards count: 52, shuffles required: 8. Cards count: 100, shuffles required: 30. Cards count: 1020, shuffles required: 1018. Cards count: 1024, shuffles required: 10. Cards count: 10000, shuffles required: 300.
Clojure
(defn perfect-shuffle [deck]
(let [half (split-at (/ (count deck) 2) deck)]
(interleave (first half) (last half))))
(defn solve [deck-size]
(let [original (range deck-size)
trials (drop 1 (iterate perfect-shuffle original))
predicate #(= original %)]
(println (format "%5s: %s" deck-size
(inc (some identity (map-indexed (fn [i x] (when (predicate x) i)) trials)))))))
(map solve [8 24 52 100 1020 1024 10000])
- Output:
8: 3 24: 11 52: 8 100: 30 1020: 1018 1024: 10 10000: 300
Common Lisp
(defun perfect-shuffle (deck)
(let* ((half (floor (length deck) 2))
(left (subseq deck 0 half))
(right (nthcdr half deck)))
(mapcan #'list left right)))
(defun solve (deck-size)
(loop with original = (loop for n from 1 to deck-size collect n)
for trials from 1
for deck = original then shuffled
for shuffled = (perfect-shuffle deck)
until (equal shuffled original)
finally (format t "~5D: ~4D~%" deck-size trials)))
(solve 8)
(solve 24)
(solve 52)
(solve 100)
(solve 1020)
(solve 1024)
(solve 10000)
- Output:
8: 3 24: 11 52: 8 100: 30 1020: 1018 1024: 10 10000: 300
D
import std.stdio;
void main() {
auto sizes = [8, 24, 52, 100, 1020, 1024, 10_000];
foreach(s; sizes) {
writefln("%5s : %5s", s, perfectShuffle(s));
}
}
int perfectShuffle(int size) {
import std.exception : enforce;
enforce(size%2==0);
import std.algorithm : copy, equal;
import std.range;
int[] orig = iota(0, size).array;
int[] process;
process.length = size;
copy(orig, process);
for(int count=1; true; count++) {
process = roundRobin(process[0..$/2], process[$/2..$]).array;
if (equal(orig, process)) {
return count;
}
}
assert(false, "How did this get here?");
}
- Output:
8 : 3 24 : 11 52 : 8 100 : 30 1020 : 1018 1024 : 10 10000 : 300
Delphi
program Perfect_shuffle;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
type
TDeck = record
Cards: TArray<Integer>;
Len: Integer;
constructor Create(deckSize: Integer); overload;
constructor Create(deck: TDeck); overload;
procedure shuffleDeck();
class operator Equal(a, b: TDeck): boolean;
function ShufflesRequired: Integer;
procedure Assign(a: TDeck);
end;
{ TDeck }
procedure TDeck.Assign(a: TDeck);
begin
Len := a.Len;
Cards := copy(a.Cards, 0, len);
end;
constructor TDeck.Create(deckSize: Integer);
begin
if deckSize < 1 then
raise Exception.Create('Error: Deck size must have above zero');
if Odd(deckSize) then
raise Exception.Create('Error: Deck size must be even');
SetLength(Cards, deckSize);
Len := deckSize;
for var i := 0 to High(Cards) do
Cards[i] := i;
end;
constructor TDeck.Create(deck: TDeck);
begin
Assign(deck);
end;
class operator TDeck.Equal(a, b: TDeck): boolean;
begin
if a.len <> b.len then
raise Exception.Create('Error: Decks aren''t equally sized');
if a.Len = 0 then
exit(True);
for var i := 0 to a.Len - 1 do
if a.Cards[i] <> b.Cards[i] then
exit(False);
Result := True;
end;
procedure TDeck.shuffleDeck;
var
tmp: TArray<Integer>;
begin
SetLength(tmp, len);
for var i := 0 to len div 2 - 1 do
begin
tmp[i * 2] := Cards[i];
tmp[i * 2 + 1] := Cards[len div 2 + i];
end;
Cards := copy(tmp, 0, len);
end;
function TDeck.ShufflesRequired: Integer;
var
ref: TDeck;
begin
Result := 1;
ref := TDeck.Create(self);
shuffleDeck;
while not (self = ref) do
begin
shuffleDeck;
inc(Result);
end;
end;
const
cases: TArray<Integer> = [8, 24, 52, 100, 1020, 1024, 10000];
begin
for var size in cases do
begin
var deck := TDeck.Create(size);
writeln(format('Cards count: %d, shuffles required: %d', [size, deck.ShufflesRequired]));
end;
readln;
end.
Dyalect
func shuffle(arr) {
if arr.Length() % 2 != 0 {
throw @InvalidValue(arr.Length())
}
var half = arr.Length() / 2
var result = Array.Empty(arr.Length())
var (t, l, r) = (0, 0, half)
while l < half {
result[t] = arr[l]
result[t+1] = arr[r]
l += 1
r += 1
t += 2
}
result
}
func arrayEqual(xs, ys) {
if xs.Length() != ys.Length() {
return false
}
for i in xs.Indices() {
if xs[i] != ys[i] {
return false
}
}
return true
}
func shuffleThrough(original) {
var copy = original.Clone()
while true {
copy = shuffle(copy)
yield copy
if arrayEqual(original, copy) {
break
}
}
}
for input in yields { 8, 24, 52, 100, 1020, 1024, 10000} {
var numbers = [1..input]
print("\(input) cards: \(shuffleThrough(numbers).Length())")
}
- Output:
8 cards: 3 24 cards: 11 52 cards: 8 100 cards: 30 1020 cards: 1018 1024 cards: 10 10000 cards: 300
EasyLang
proc pshuffle . deck[] .
mp = len deck[] / 2
in[] = deck[]
for i = 1 to mp
deck[2 * i - 1] = in[i]
deck[2 * i] = in[i + mp]
.
.
proc test size . .
for i to size
deck0[] &= i
.
deck[] = deck0[]
repeat
pshuffle deck[]
cnt += 1
until deck[] = deck0[]
.
print cnt
.
for size in [ 8 24 52 100 1020 1024 10000 ]
test size
.
EchoLisp
;; shuffler : a permutation vector which interleaves both halves of deck
(define (make-shuffler n)
(let ((s (make-vector n)))
(for ((i (in-range 0 n 2))) (vector-set! s i (/ i 2)))
(for ((i (in-range 0 n 2))) (vector-set! s (1+ i) (+ (/ n 2) (vector-ref s i))))
s))
;; output : (n . # of shuffles needed to go back)
(define (magic-shuffle n)
(when (odd? n) (error "magic-shuffle:odd input" n))
(let [(deck (list->vector (iota n))) ;; (0 1 ... n-1)
(dock (list->vector (iota n))) ;; keep trace or init deck
(shuffler (make-shuffler n))]
(cons n (1+
(for/sum ((i Infinity)) ; (in-naturals missing in EchoLisp v2.9)
(vector-permute! deck shuffler) ;; permutes in place
#:break (eqv? deck dock) ;; compare to first
1)))))
- Output:
map magic-shuffle '(8 24 52 100 1020 1024 10000))
→ ((8 . 3) (24 . 11) (52 . 8) (100 . 30) (1020 . 1018) (1024 . 10) (10000 . 300))
;; Let's look in the On-line Encyclopedia of Integer Sequences
;; Given a list of numbers, the (oeis ...) function looks for a sequence
(lib 'web)
Lib: web.lib loaded.
map magic-shuffle (range 2 18 2))
→ ((2 . 1) (4 . 2) (6 . 4) (8 . 3) (10 . 6) (12 . 10) (14 . 12) (16 . 4))
(oeis '(1 2 4 3 6 10 12 4))
→ Sequence A002326 found
Elixir
defmodule Perfect do
def shuffle(n) do
start = Enum.to_list(1..n)
m = div(n, 2)
shuffle(start, magic_shuffle(start, m), m, 1)
end
defp shuffle(start, start, _, step), do: step
defp shuffle(start, deck, m, step) do
shuffle(start, magic_shuffle(deck, m), m, step+1)
end
defp magic_shuffle(deck, len) do
{left, right} = Enum.split(deck, len)
Enum.zip(left, right)
|> Enum.map(&Tuple.to_list/1)
|> List.flatten
end
end
Enum.each([8, 24, 52, 100, 1020, 1024, 10000], fn n ->
step = Perfect.shuffle(n)
IO.puts "#{n} : #{step}"
end)
- Output:
8 : 3 24 : 11 52 : 8 100 : 30 1020 : 1018 1024 : 10 10000 : 300
F#
let perfectShuffle xs =
let h = (List.length xs) / 2
xs
|> List.mapi (fun i x->(if i<h then i * 2 else ((i-h) * 2) + 1), x)
|> List.sortBy fst
|> List.map snd
let orderCount n =
let xs = [1..n]
let rec spin count ys =
if xs=ys then count
else ys |> perfectShuffle |> spin (count + 1)
xs |> perfectShuffle |> spin 1
[ 8; 24; 52; 100; 1020; 1024; 10000 ] |> List.iter (fun n->n |> orderCount |> printfn "%d %d" n)
- Output:
8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
Factor
USING: arrays formatting kernel math prettyprint sequences
sequences.merged ;
IN: rosetta-code.perfect-shuffle
CONSTANT: test-cases { 8 24 52 100 1020 1024 10000 }
: shuffle ( seq -- seq' ) halves 2merge ;
: shuffle-count ( n -- m )
<iota> >array 0 swap dup [ 2dup = ] [ shuffle [ 1 + ] 2dip ]
do until 2drop ;
"Deck size" "Number of shuffles required" "%-11s %-11s\n" printf
test-cases [ dup shuffle-count "%-11d %-11d\n" printf ] each
- Output:
Deck size Number of shuffles required 8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
Fortran
MODULE PERFECT_SHUFFLE
IMPLICIT NONE
CONTAINS
! Shuffle the deck/array of integers
FUNCTION SHUFFLE(NUM_ARR)
INTEGER, DIMENSION(:), INTENT(IN) :: NUM_ARR
INTEGER, DIMENSION(SIZE(NUM_ARR)) :: SHUFFLE
INTEGER :: I, IDX
IF (MOD(SIZE(NUM_ARR), 2) .NE. 0) THEN
WRITE(*,*) "ERROR: SIZE OF DECK MUST BE EVEN NUMBER"
CALL EXIT(1)
END IF
IDX = 1
DO I=1, SIZE(NUM_ARR)/2
SHUFFLE(IDX) = NUM_ARR(I)
SHUFFLE(IDX+1) = NUM_ARR(SIZE(NUM_ARR)/2+I)
IDX = IDX + 2
END DO
END FUNCTION SHUFFLE
! Compare two arrays element by element
FUNCTION COMPARE_ARRAYS(ARRAY_1, ARRAY_2)
INTEGER, DIMENSION(:) :: ARRAY_1, ARRAY_2
LOGICAL :: COMPARE_ARRAYS
INTEGER :: I
DO I=1,SIZE(ARRAY_1)
IF (ARRAY_1(I) .NE. ARRAY_2(I)) THEN
COMPARE_ARRAYS = .FALSE.
RETURN
END IF
END DO
COMPARE_ARRAYS = .TRUE.
END FUNCTION COMPARE_ARRAYS
! Generate a deck/array of consecutive integers
FUNCTION GEN_DECK(DECK_SIZE)
INTEGER, INTENT(IN) :: DECK_SIZE
INTEGER, DIMENSION(DECK_SIZE) :: GEN_DECK
INTEGER :: I
GEN_DECK = (/(I, I=1,DECK_SIZE)/)
END FUNCTION GEN_DECK
END MODULE PERFECT_SHUFFLE
! Program to demonstrate the perfect shuffle algorithm
! for various deck sizes
PROGRAM DEMO_PERFECT_SHUFFLE
USE PERFECT_SHUFFLE
IMPLICIT NONE
INTEGER, PARAMETER, DIMENSION(7) :: DECK_SIZES = (/8, 24, 52, 100, 1020, 1024, 10000/)
INTEGER, DIMENSION(:), ALLOCATABLE :: DECK, SHUFFLED
INTEGER :: I, COUNTER
WRITE(*,'(A, A, A)') "input (deck size)", " | ", "output (number of shuffles required)"
WRITE(*,*) REPEAT("-", 55)
DO I=1, SIZE(DECK_SIZES)
IF (I .GT. 1) THEN
DEALLOCATE(DECK)
DEALLOCATE(SHUFFLED)
END IF
ALLOCATE(DECK(DECK_SIZES(I)))
ALLOCATE(SHUFFLED(DECK_SIZES(I)))
DECK = GEN_DECK(DECK_SIZES(I))
SHUFFLED = SHUFFLE(DECK)
COUNTER = 1
DO WHILE (.NOT. COMPARE_ARRAYS(DECK, SHUFFLED))
SHUFFLED = SHUFFLE(SHUFFLED)
COUNTER = COUNTER + 1
END DO
WRITE(*,'(I17, A, I35)') DECK_SIZES(I), " | ", COUNTER
END DO
END PROGRAM DEMO_PERFECT_SHUFFLE
input (deck size) | output (number of shuffles required) ------------------------------------------------------- 8 | 3 24 | 11 52 | 8 100 | 30 1020 | 1018 1024 | 10 10000 | 300
FreeBASIC
function is_in_order( d() as uinteger ) as boolean
'tests if a deck is in order
for i as uinteger = lbound(d) to ubound(d)-1
if d(i) > d(i+1) then return false
next i
return true
end function
sub init_deck( d() as uinteger )
for i as uinteger = 1 to ubound(d)
d(i) = i
next i
return
end sub
sub shuffle( d() as uinteger )
'does a faro shuffle of the deck
dim as integer n = ubound(d), i
dim as integer b( 1 to n )
for i = 1 to n/2
b(2*i-1) = d(i)
b(2*i) = d(n/2+i)
next i
for i = 1 to n
d(i) = b(i)
next i
return
end sub
function shufs_needed( size as integer ) as uinteger
dim as uinteger d(1 to size), s = 0
init_deck(d())
do
shuffle(d())
s+=1
if is_in_order(d()) then exit do
loop
return s
end function
dim as uinteger tests(1 to 7) = {8, 24, 52, 100, 1020, 1024, 10000}, i
for i = 1 to 7
print tests(i);" cards require "; shufs_needed(tests(i)); " shuffles."
next i
- Output:
8 cards require 3 shuffles. 24 cards require 11 shuffles. 52 cards require 8 shuffles. 100 cards require 30 shuffles. 1020 cards require 1018 shuffles. 1024 cards require 10 shuffles. 10000 cards require 300 shuffles.
Go
package main
import "fmt"
type Deck struct {
Cards []int
length int
}
func NewDeck(deckSize int) (res *Deck){
if deckSize % 2 != 0{
panic("Deck size must be even")
}
res = new(Deck)
res.Cards = make([]int, deckSize)
res.length = deckSize
for i,_ := range res.Cards{
res.Cards[i] = i
}
return
}
func (d *Deck)shuffleDeck(){
tmp := make([]int,d.length)
for i := 0;i <d.length/2;i++ {
tmp[i*2] = d.Cards[i]
tmp[i*2+1] = d.Cards[d.length / 2 + i]
}
d.Cards = tmp
}
func (d *Deck) isEqualTo(c Deck) (res bool) {
if d.length != c.length {
panic("Decks aren't equally sized")
}
res = true
for i, v := range d.Cards{
if v != c.Cards[i] {
res = false
}
}
return
}
func main(){
for _,v := range []int{8,24,52,100,1020,1024,10000} {
fmt.Printf("Cards count: %d, shuffles required: %d\n",v,ShufflesRequired(v))
}
}
func ShufflesRequired(deckSize int)(res int){
deck := NewDeck(deckSize)
Ref := *deck
deck.shuffleDeck()
res++
for ;!deck.isEqualTo(Ref);deck.shuffleDeck(){
res++
}
return
}
- Output:
Cards count: 8, shuffles required: 3 Cards count: 24, shuffles required: 11 Cards count: 52, shuffles required: 8 Cards count: 100, shuffles required: 30 Cards count: 1020, shuffles required: 1018 Cards count: 1024, shuffles required: 10 Cards count: 10000, shuffles required: 300
Haskell
shuffle :: [a] -> [a]
shuffle lst = let (a,b) = splitAt (length lst `div` 2) lst
in foldMap (\(x,y) -> [x,y]) $ zip a b
findCycle :: Eq a => (a -> a) -> a -> [a]
findCycle f x = takeWhile (/= x) $ iterate f (f x)
main = mapM_ report [ 8, 24, 52, 100, 1020, 1024, 10000 ]
where
report n = putStrLn ("deck of " ++ show n ++ " cards: "
++ show (countSuffles n) ++ " shuffles!")
countSuffles n = 1 + length (findCycle shuffle [1..n])
- Output:
deck of 8 cards: 3 shuffles! deck of 24 cards: 11 shuffles! deck of 52 cards: 8 shuffles! deck of 100 cards: 30 shuffles! deck of 1020 cards: 1018 shuffles! deck of 1024 cards: 10 shuffles! deck of 10000 cards: 300 shuffles!
J
The shuffle routine:
shuf=: /: $ /:@$ 0 1"_
Here, the phrase ($ $ 0 1"_) would generate a sequence of 0s and 1s the same length as the argument sequence:
($ $ 0 1"_) 'abcdef'
0 1 0 1 0 1
And we can use grade up (/:)
to find the indices which would sort the argument sequence so that the values in the positions corresponding to our generated zeros would come before the values in the positions corresponding to our ones.
/: ($ $ 0 1"_) 'abcdef'
0 2 4 1 3 5
But we can use grade up again to find what would have been the original permutation (grade up is a self inverting function for this domain).
/:/: ($ $ 0 1"_) 'abcdef'
0 3 1 4 2 5
And, that means it can also sort the original sequence into that order:
shuf 'abcdef'
adbecf
shuf 'abcdefgh'
aebfcgdh
And this will work for sequences of arbitrary length.
(The rest of the implementation of shuf
is pure syntactic sugar - you can use J's dissect and trace facilities to see the details if you are trying to learn the language.)
Meanwhile, the cycle length routine could look like this:
shuflen=: [: *./ #@>@C.@shuf@i.
Here, we first generate a list of integers of the required length in their natural order. We then reorder them using our shuf
function, find the cycles which result, find the lengths of each of these cycles then find the least common multiple of those lengths.
So here is the task example (with most of the middle trimmed out to avoid crashing the rosettacode wiki implementation):
shuflen"0 }.2*i.5000
1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 20 14 12 23 21 8 52 20 18 ... 4278 816 222 1332 384
Task example:
('deck size';'required shuffles'),(; shuflen)&> 8 24 52 100 1020 1024 10000
┌─────────┬─────────────────┐
│deck size│required shuffles│
├─────────┼─────────────────┤
│8 │3 │
├─────────┼─────────────────┤
│24 │11 │
├─────────┼─────────────────┤
│52 │8 │
├─────────┼─────────────────┤
│100 │30 │
├─────────┼─────────────────┤
│1020 │1018 │
├─────────┼─────────────────┤
│1024 │10 │
├─────────┼─────────────────┤
│10000 │300 │
└─────────┴─────────────────┘
Note that the implementation of shuf
defines a behavior for odd length "decks". Experimentation shows that cycle length for an odd length deck is often the same as the cycle length for an even length deck which is one "card" longer.
Java
import java.util.Arrays;
import java.util.stream.IntStream;
public class PerfectShuffle {
public static void main(String[] args) {
int[] sizes = {8, 24, 52, 100, 1020, 1024, 10_000};
for (int size : sizes)
System.out.printf("%5d : %5d%n", size, perfectShuffle(size));
}
static int perfectShuffle(int size) {
if (size % 2 != 0)
throw new IllegalArgumentException("size must be even");
int half = size / 2;
int[] a = IntStream.range(0, size).toArray();
int[] original = a.clone();
int[] aa = new int[size];
for (int count = 1; true; count++) {
System.arraycopy(a, 0, aa, 0, size);
for (int i = 0; i < half; i++) {
a[2 * i] = aa[i];
a[2 * i + 1] = aa[i + half];
}
if (Arrays.equals(a, original))
return count;
}
}
}
8 : 3 24 : 11 52 : 8 100 : 30 1020 : 1018 1024 : 10 10000 : 300
JavaScript
ES6
(() => {
'use strict';
// shuffleCycleLength :: Int -> Int
const shuffleCycleLength = deckSize =>
firstCycle(shuffle, range(1, deckSize))
.all.length;
// shuffle :: [a] -> [a]
const shuffle = xs =>
concat(zip.apply(null, splitAt(div(length(xs), 2), xs)));
// firstycle :: Eq a => (a -> a) -> a -> [a]
const firstCycle = (f, x) =>
until(
m => EqArray(x, m.current),
m => {
const fx = f(m.current);
return {
current: fx,
all: m.all.concat([fx])
};
}, {
current: f(x),
all: [x]
}
);
// Two arrays equal ?
// EqArray :: [a] -> [b] -> Bool
const EqArray = (xs, ys) => {
const [nx, ny] = [xs.length, ys.length];
return nx === ny ? (
nx > 0 ? (
xs[0] === ys[0] && EqArray(xs.slice(1), ys.slice(1))
) : true
) : false;
};
// GENERIC FUNCTIONS
// zip :: [a] -> [b] -> [(a,b)]
const zip = (xs, ys) =>
xs.slice(0, Math.min(xs.length, ys.length))
.map((x, i) => [x, ys[i]]);
// concat :: [[a]] -> [a]
const concat = xs => [].concat.apply([], xs);
// splitAt :: Int -> [a] -> ([a],[a])
const splitAt = (n, xs) => [xs.slice(0, n), xs.slice(n)];
// div :: Num -> Num -> Int
const div = (x, y) => Math.floor(x / y);
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = (p, f, x) => {
const go = x => p(x) ? x : go(f(x));
return go(x);
}
// range :: Int -> Int -> [Int]
const range = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
// length :: [a] -> Int
// length :: Text -> Int
const length = xs => xs.length;
// maximumBy :: (a -> a -> Ordering) -> [a] -> a
const maximumBy = (f, xs) =>
xs.reduce((a, x) => a === undefined ? x : (
f(x, a) > 0 ? x : a
), undefined);
// transpose :: [[a]] -> [[a]]
const transpose = xs =>
xs[0].map((_, iCol) => xs.map((row) => row[iCol]));
// show :: a -> String
const show = x => JSON.stringify(x, null, 2);
// replicateS :: Int -> String -> String
const replicateS = (n, s) => {
let v = s,
o = '';
if (n < 1) return o;
while (n > 1) {
if (n & 1) o = o.concat(v);
n >>= 1;
v = v.concat(v);
}
return o.concat(v);
};
// justifyRight :: Int -> Char -> Text -> Text
const justifyRight = (n, cFiller, strText) =>
n > strText.length ? (
(replicateS(n, cFiller) + strText)
.slice(-n)
) : strText;
// TEST
return transpose(transpose([
['Deck', 'Shuffles']
].concat(
[8, 24, 52, 100, 1020, 1024, 10000]
.map(n => [n.toString(), shuffleCycleLength(n)
.toString()
])))
.map(col => { // Right-justified number columns
const width = length(
maximumBy((a, b) => length(a) - length(b), col)
) + 2;
return col.map(x => justifyRight(width, ' ', x));
}))
.map(row => row.join(''))
.join('\n');
})();
- Output:
Deck Shuffles 8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
jq
A small point of interest in the following is the `recurrence` function as it is generic.
def perfect_shuffle:
. as $a
| if (length % 2) == 1 then "cannot perform perfect shuffle on odd-length array" | error
else (length / 2) as $mid
| reduce range(0; $mid) as $i (null;
.[2*$i] = $a[$i]
| .[2*$i + 1] = $a[$mid+$i] )
end;
# How many iterations of f are required to get back to . ?
def recurrence(f):
def r:
# input: [$init, $current, $count]
(.[1]|f) as $next
| if .[0] == $next then .[-1] + 1
else [.[0], $next, .[-1]+1] | r
end;
[., ., 0] | r;
def count_perfect_shuffles:
[range(0;.)] | recurrence(perfect_shuffle);
(8, 24, 52, 100, 1020, 1024, 10000, 100000)
| [., count_perfect_shuffles]
- Output:
[8,3] [24,11] [52,8] [100,30] [1020,1018] [1024,10] [10000,300] [100000,540]
Julia
using Printf
function perfect_shuffle(a::Array)::Array
if isodd(length(a)) error("cannot perform perfect shuffle on odd-length array") end
rst = zeros(a)
mid = div(length(a), 2)
for i in 1:mid
rst[2i-1], rst[2i] = a[i], a[mid+i]
end
return rst
end
function count_perfect_shuffles(decksize::Int)::Int
a = collect(1:decksize)
b, c = perfect_shuffle(a), 1
while a != b
b = perfect_shuffle(b)
c += 1
end
return c
end
println(" Deck n.Shuffles")
for i in (8, 24, 52, 100, 1020, 1024, 10000, 100000)
count = count_perfect_shuffles(i)
@printf("%7i%7i\n", i, count)
end
- Output:
Deck n.Shuffles 8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300 100000 540
Kotlin
// version 1.1.2
fun areSame(a: IntArray, b: IntArray): Boolean {
for (i in 0 until a.size) if (a[i] != b[i]) return false
return true
}
fun perfectShuffle(a: IntArray): IntArray {
var b = IntArray(a.size)
val hSize = a.size / 2
for (i in 0 until hSize) b[i * 2] = a[i]
var j = 1
for (i in hSize until a.size) {
b[j] = a[i]
j += 2
}
return b
}
fun countShuffles(a: IntArray): Int {
require(a.size >= 2 && a.size % 2 == 0)
var b = a
var count = 0
while (true) {
val c = perfectShuffle(b)
count++
if (areSame(a, c)) return count
b = c
}
}
fun main(args: Array<String>) {
println("Deck size Num shuffles")
println("--------- ------------")
val sizes = intArrayOf(8, 24, 52, 100, 1020, 1024, 10000)
for (size in sizes) {
val a = IntArray(size) { it }
val count = countShuffles(a)
println("${"%-9d".format(size)} $count")
}
}
- Output:
Deck size Num shuffles --------- ------------ 8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
Lua
-- Perform weave shuffle
function shuffle (cards)
local pile1, pile2 = {}, {}
for card = 1, #cards / 2 do table.insert(pile1, cards[card]) end
for card = (#cards / 2) + 1, #cards do table.insert(pile2, cards[card]) end
cards = {}
for card = 1, #pile1 do
table.insert(cards, pile1[card])
table.insert(cards, pile2[card])
end
return cards
end
-- Return boolean indicating whether or not the cards are in order
function inOrder (cards)
for k, v in pairs(cards) do
if k ~= v then return false end
end
return true
end
-- Count the number of shuffles needed before the cards are in order again
function countShuffles (deckSize)
local deck, count = {}, 0
for i = 1, deckSize do deck[i] = i end
repeat
deck = shuffle(deck)
count = count + 1
until inOrder(deck)
return count
end
-- Main procedure
local testCases = {8, 24, 52, 100, 1020, 1024, 10000}
print("Input", "Output")
for _, case in pairs(testCases) do print(case, countShuffles(case)) end
- Output:
Input Output 8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
Mathematica/Wolfram Language
shuffle[deck_] := Apply[Riffle, TakeDrop[deck, Length[deck]/2]];
shuffleCount[n_] := Block[{count=0}, NestWhile[shuffle, shuffle[Range[n]], (count++; OrderedQ[#] )&];count];
Map[shuffleCount, {8, 24, 52, 100, 1020, 1024, 10000}]
- Output:
{3, 11, 8, 30, 1018, 10, 300}
MATLAB
PerfectShuffle.m:
function [New]=PerfectShuffle(Nitems, Nturns)
if mod(Nitems,2)==0 %only if even number
X=1:Nitems; %define deck
for c=1:Nturns %defines one shuffle
X=reshape(X,Nitems/2,2)'; %split the deck in two and stack halves
X=X(:)'; %mix the halves
end
New=X; %result of multiple shufflings
end
Main:
Result=[]; %vector to store results
Q=[8, 24, 52, 100, 1020, 1024, 10000]; %queries
for n=Q %for each query
Same=0; %initialize comparison
T=0; %initialize number of shuffles
while ~Same %while the result is not the original query
T=T+1; %one more shuffle
R=PerfectShuffle(n,T); %result of shuffling the query
Same=~(any(R-(1:n))); %same vector as the query
end %when getting the same vector
Result=[Result;T]; %collect results
end
disp([Q', Result])
- Output:
8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
Modula-2
MODULE PerfectShuffle;
FROM FormatString IMPORT FormatString;
FROM Storage IMPORT ALLOCATE,DEALLOCATE;
FROM SYSTEM IMPORT ADDRESS,TSIZE;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
PROCEDURE WriteCard(c : CARDINAL);
VAR buf : ARRAY[0..15] OF CHAR;
BEGIN
FormatString("%c", buf, c);
WriteString(buf)
END WriteCard;
PROCEDURE Init(VAR arr : ARRAY OF INTEGER);
VAR i : CARDINAL;
BEGIN
FOR i:=0 TO HIGH(arr) DO
arr[i] := i + 1
END
END Init;
PROCEDURE PerfectShuffle(VAR arr : ARRAY OF INTEGER);
PROCEDURE Inner(ti : CARDINAL);
VAR
tv : INTEGER;
tp,tn,n : CARDINAL;
BEGIN
n := HIGH(arr);
tn := ti;
tv := arr[ti];
REPEAT
tp := tn;
IF tp MOD 2 = 0 THEN
tn := tp / 2
ELSE
tn := (n+1)/2+tp/2
END;
arr[tp] := arr[tn];
UNTIL tn = ti;
arr[tp] := tv
END Inner;
VAR
done : BOOLEAN;
i,c : CARDINAL;
BEGIN
c := 0;
Init(arr);
REPEAT
i := 1;
WHILE i <= (HIGH(arr)/2) DO
Inner(i);
INC(i,2)
END;
INC(c);
done := TRUE;
FOR i:=0 TO HIGH(arr) DO
IF arr[i] # INT(i+1) THEN
done := FALSE;
BREAK
END
END
UNTIL done;
WriteCard(HIGH(arr)+1);
WriteString(": ");
WriteCard(c);
WriteLn
END PerfectShuffle;
(* Main *)
VAR
v8 : ARRAY[1..8] OF INTEGER;
v24 : ARRAY[1..24] OF INTEGER;
v52 : ARRAY[1..52] OF INTEGER;
v100 : ARRAY[1..100] OF INTEGER;
v1020 : ARRAY[1..1020] OF INTEGER;
v1024 : ARRAY[1..1024] OF INTEGER;
v10000 : ARRAY[1..10000] OF INTEGER;
BEGIN
PerfectShuffle(v8);
PerfectShuffle(v24);
PerfectShuffle(v52);
PerfectShuffle(v100);
PerfectShuffle(v1020);
PerfectShuffle(v1024);
PerfectShuffle(v10000);
ReadChar
END PerfectShuffle.
- Output:
8: 3 24: 11 52: 8 100: 30 1020: 1018 1024: 10 10000: 300
Nim
import sequtils, strutils
proc newValList(size: Positive): seq[int] =
if (size and 1) != 0:
raise newException(ValueError, "size must be even.")
result = toSeq(1..size)
func shuffled(list: seq[int]): seq[int] =
result.setLen(list.len)
let half = list.len div 2
for i in 0..<half:
result[2 * i] = list[i]
result[2 * i + 1] = list[half + i]
for size in [8, 24, 52, 100, 1020, 1024, 10000]:
let initList = newValList(size)
var valList = initList
var count = 0
while true:
inc count
valList = shuffled(valList)
if valList == initList:
break
echo ($size).align(5), ": ", ($count).align(4)
- Output:
8: 3 24: 11 52: 8 100: 30 1020: 1018 1024: 10 10000: 300
Oforth
: shuffle(l) l size 2 / dup l left swap l right zip expand ;
: nbShuffles(l) 1 l while( shuffle dup l <> ) [ 1 under+ ] drop ;
- Output:
>[ 8, 24, 52, 100, 1020, 1024, 10000 ] map(#[ seq nbShuffles ]) . [3, 11, 8, 30, 1018, 10, 300] ok
PARI/GP
magic(v)=vector(#v,i,v[if(i%2,1,#v/2)+i\2]);
shuffles_slow(n)=my(v=[1..n],o=v,s=1);while((v=magic(v))!=o,s++);s;
shuffles(n)=znorder(Mod(2,n-1));
vector(5000,n,shuffles_slow(2*n))
- Output:
%1 = [1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6, 12, 66, 22, 35, 9, 20, 30, 39, 54 , 82, 8, 28, 11, 12, 10, 36, 48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 1 10, 20, 100, 7, 14, 130, 18, 36, 68, 138, 46, 60, 28, 42, 148, 15, 24, 20, 52, 5 2, 33, 162, 20, 83, 156, 18, 172, 60, 58, 178, 180, 60, 36, 40, 18, 95, 96, 12, 196, 99, 66, 84, 20, 66, 90, 210, 70, 28, 15, 18, 24, 37, 60, 226, 76, 30, 29, 9 2, 78, 119, 24, 162, 84, 36, 82, 50, 110, 8, 16, 36, 84, 131, 52, 22, 268, 135, 12, 20, 92, 30, 70, 94, 36, 60, 136, 48, 292, 116, 90, 132, 42, 100, 60, 102, 10 2, 155, 156, 12, 316, 140, 106, 72, 60, 36, 69, 30, 36, 132, 21, 28, 10, 147, 44 , 346, 348, 36, 88, 140, 24, 179, 342, 110, 36, 183, 60, 156, 372, 100, 84, 378, 14, 191, 60, 42, 388, 88, 130, 156, 44, 18, 200, 60, 108, 180, 204, 68, 174, 16 4, 138, 418, 420, 138, 40, 60, 60, 43, 72, 28, 198, 73, 42, 442, 44, 148, 224, 2 0, 30, 12, 76, 72, 460, 231, 20, 466, 66, 52, 70, 180, 156, 239, 36, 66, 48, 243 , 162, 490, 56, 60, 105, 166, 166, 251, 100, 156, 508, 9, 18, 204, 230, 172, 260 , 522, 60, 40, 253, 174, 60, 212, 178, 210, 540, 180, 36, 546, 60, 252, 39, 36, 556, 84, 40, 562, 28, 54, 284, 114, 190, 220, 144, 96, 246, 260, 12, 586, 90, 19 6, 148, 24, 198, 299, 25, 66, 220, 303, 84, 276, 612, 20, 154, 618, 198, 33, 500 , 90, 72, 45, 210, 28, 84, 210, 64, 214, 28, 323, 290, 30, 652, 260, 18, 658, 66 0, 24, 36, 308, 74, 60, 48, 180, 676, 48, 226, 22, 68, 76, 156, 230, 30, 276, 40 , 58, 700, 36, 92, 300, 708, 78, 55, 60, 238, 359, 51, 24, 140, 121, 486, 56, 24 4, 84, 330, 246, 36, 371, 148, 246, 318, 375, 50, 60, 756, 110, 380, 36, 24, 348 , 384, 16, 772, 20, 36, 180, 70, 252, 52, 786, 262, 84, 60, 52, 796, 184, 66, 90 , 132, 268, 404, 270, 270, 324, 126, 12, 820, 411, 20, 826, 828, 92, 168, 332, 9 0, 419, 812, 70, 156, 330, 94, 396, 852, 36, 428, 858, 60, 431, 172, 136, 390, 1 32, 48, 300, 876, 292, 55, 882, 116, 443, 21, 270, 414, 356, 132, 140, 104,[+++]
(By default gp won't show more than 25 lines of output, though an arbitrary amount can be printed or written to a file; use print
, write
, or default(lines, 100)
to show more.)
Perl
use v5.36;
use List::Util 'all';
sub perfect_shuffle (@deck) {
my $middle = @deck / 2;
map { @deck[$_, $_ + $middle] } 0..$middle-1;
}
for my $size (8, 24, 52, 100, 1020, 1024, 10000) {
my @shuffled = my @deck = 1..$size;
my $n;
do { $n++; @shuffled = perfect_shuffle @shuffled }
until all { $shuffled[$_] == $deck[$_] } 0..$#shuffled;
printf "%5d cards: %4d\n", $size, $n;
}
- Output:
8 cards: 3 24 cards: 11 52 cards: 8 100 cards: 30 1020 cards: 1018 1024 cards: 10 10000 cards: 300
Phix
with javascript_semantics function perfect_shuffle(sequence deck) integer l = length(deck), mp = l/2, k = 1 sequence res = repeat(0,l) for i=1 to mp do res[k] = deck[i] k += 1 res[k] = deck[i+mp] k += 1 end for return res end function constant testsizes = {8, 24, 52, 100, 1020, 1024, 10000} for i=1 to length(testsizes) do sequence deck = tagset(testsizes[i]) sequence work = perfect_shuffle(deck) integer count = 1 while work!=deck do work = perfect_shuffle(work) count += 1 end while printf(1,"%5d cards: %4d\n", {testsizes[i],count}) end for
- Output:
8 cards: 3 24 cards: 11 52 cards: 8 100 cards: 30 1020 cards: 1018 1024 cards: 10 10000 cards: 300
Picat
A perfect shuffle can be done in two ways:
- in: first card in top half is the first card in the new deck
- out: first card in bottom half is the first card in the new deck
The method used here supports both shuffle types. The task states an out shuffling.
Out shuffle
go =>
member(N,[8,24,52,100,1020,1024,10_000]),
println(n=N),
InOut = out, % in/out shuffling
println(inOut=InOut),
Print = cond(N < 100, true,false),
if Print then
println(1..N),
end,
Count = show_all_shuffles(N,InOut,Print),
println(count=Count),
nl,
fail,
nl.
%
% Show all the shuffles
%
show_all_shuffles(N,InOut) = show_all_shuffles(N,InOut,false).
show_all_shuffles(N,InOut,Print) = Count =>
Order = 1..N,
Perfect1 = perfect_shuffle(1..N,InOut),
Perfect = copy_term(Perfect1),
if Print == true then
println(Perfect)
end,
Count = 1,
while (Perfect != Order)
Perfect := [Perfect1[Perfect[I]] : I in 1..N],
if Print == true then
println(Perfect)
end,
Count := Count + 1
end.
%
% Perfect shuffle a list
%
% InOut = in|out
% in: first card in Top half is the first card in the new deck
% out: first card in Bottom half is the first card in the new deck
%
perfect_shuffle(List,InOut) = Perfect =>
[Top,Bottom] = split_deck(List,InOut),
if InOut = out then
Perfect = zip2(Top,Bottom)
else
Perfect = zip2(Bottom,Top)
end.
%
% split the deck in two "halves"
%
% For odd out shuffles, we have to adjust the
% range of the top and bottom.
%
split_deck(L,InOut) = [Top,Bottom] =>
N = L.len,
if InOut = out, N mod 2 = 1 then
Top = 1..(N div 2)+1,
Bottom = (N div 2)+2..N
else
Top = 1..(N div 2),
Bottom = (N div 2)+1..N
end.
%
% If L1 and L2 has uneven lengths, we add the odd element last
% in the resulting list.
%
zip2(L1,L2) = R =>
L1Len = L1.len,
L2Len = L2.len,
R1 = [],
foreach(I in 1..min(L1Len,L2Len))
R1 := R1 ++ [L1[I],L2[I]]
end,
if L1Len < L2Len then
R1 := R1 ++ [L2[L2Len]]
elseif L1Len > L2Len then
R1 := R1 ++ [L1[L1Len]]
end,
R = R1.
- Output:
n = 8 inOut = out [1,2,3,4,5,6,7,8] [1,5,2,6,3,7,4,8] [1,3,5,7,2,4,6,8] [1,2,3,4,5,6,7,8] count = 3 n = 24 inOut = out [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24] [1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,11,23,12,24] [1,7,13,19,2,8,14,20,3,9,15,21,4,10,16,22,5,11,17,23,6,12,18,24] [1,4,7,10,13,16,19,22,2,5,8,11,14,17,20,23,3,6,9,12,15,18,21,24] [1,14,4,17,7,20,10,23,13,3,16,6,19,9,22,12,2,15,5,18,8,21,11,24] [1,19,14,9,4,22,17,12,7,2,20,15,10,5,23,18,13,8,3,21,16,11,6,24] [1,10,19,5,14,23,9,18,4,13,22,8,17,3,12,21,7,16,2,11,20,6,15,24] [1,17,10,3,19,12,5,21,14,7,23,16,9,2,18,11,4,20,13,6,22,15,8,24] [1,9,17,2,10,18,3,11,19,4,12,20,5,13,21,6,14,22,7,15,23,8,16,24] [1,5,9,13,17,21,2,6,10,14,18,22,3,7,11,15,19,23,4,8,12,16,20,24] [1,3,5,7,9,11,13,15,17,19,21,23,2,4,6,8,10,12,14,16,18,20,22,24] [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24] count = 11 n = 52 inOut = out [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52] [1,27,2,28,3,29,4,30,5,31,6,32,7,33,8,34,9,35,10,36,11,37,12,38,13,39,14,40,15,41,16,42,17,43,18,44,19,45,20,46,21,47,22,48,23,49,24,50,25,51,26,52] [1,14,27,40,2,15,28,41,3,16,29,42,4,17,30,43,5,18,31,44,6,19,32,45,7,20,33,46,8,21,34,47,9,22,35,48,10,23,36,49,11,24,37,50,12,25,38,51,13,26,39,52] [1,33,14,46,27,8,40,21,2,34,15,47,28,9,41,22,3,35,16,48,29,10,42,23,4,36,17,49,30,11,43,24,5,37,18,50,31,12,44,25,6,38,19,51,32,13,45,26,7,39,20,52] [1,17,33,49,14,30,46,11,27,43,8,24,40,5,21,37,2,18,34,50,15,31,47,12,28,44,9,25,41,6,22,38,3,19,35,51,16,32,48,13,29,45,10,26,42,7,23,39,4,20,36,52] [1,9,17,25,33,41,49,6,14,22,30,38,46,3,11,19,27,35,43,51,8,16,24,32,40,48,5,13,21,29,37,45,2,10,18,26,34,42,50,7,15,23,31,39,47,4,12,20,28,36,44,52] [1,5,9,13,17,21,25,29,33,37,41,45,49,2,6,10,14,18,22,26,30,34,38,42,46,50,3,7,11,15,19,23,27,31,35,39,43,47,51,4,8,12,16,20,24,28,32,36,40,44,48,52] [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52] [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52] count = 8 n = 100 inOut = out count = 30 n = 1020 inOut = out count = 1018 n = 1024 inOut = out count = 10 n = 10000 inOut = out count = 300
In shuffle
Here's an example of an in shuffle. It takes 6 shuffles to get an 8 card deck back to its original order (compare with 3 for an out shuffle).
main =>
N = 8,
println(1..N),
InOut = in, % in shuffling
Count = show_all_shuffles(N,InOut,true),
println(count=Count),
nl.
- Output:
[1,2,3,4,5,6,7,8] [5,1,6,2,7,3,8,4] [7,5,3,1,8,6,4,2] [8,7,6,5,4,3,2,1] [4,8,3,7,2,6,1,5] [2,4,6,8,1,3,5,7] [1,2,3,4,5,6,7,8] count = 6
Uneven decks
The method supports decks of uneven lengths, here size 11 (using an out shuffle).
main =>
N = 11,
println(1..N),
InOut = out, % in/out shuffling
Count = show_all_shuffles(N,InOut,true),
println(count=Count),
nl.
- Output:
[1,2,3,4,5,6,7,8,9,10,11] [1,7,2,8,3,9,4,10,5,11,6] [1,4,7,10,2,5,8,11,3,6,9] [1,8,4,11,7,3,10,6,2,9,5] [1,10,8,6,4,2,11,9,7,5,3] [1,11,10,9,8,7,6,5,4,3,2] [1,6,11,5,10,4,9,3,8,2,7] [1,9,6,3,11,8,5,2,10,7,4] [1,5,9,2,6,10,3,7,11,4,8] [1,3,5,7,9,11,2,4,6,8,10] [1,2,3,4,5,6,7,8,9,10,11] count = 10
PicoLisp
(de perfectShuffle (Lst)
(mapcan '((B A) (list A B))
(cdr (nth Lst (/ (length Lst) 2)))
Lst ) )
(for N (8 24 52 100 1020 1024 10000)
(let (Lst (range 1 N) L Lst Cnt 1)
(until (= Lst (setq L (perfectShuffle L)))
(inc 'Cnt) )
(tab (5 6) N Cnt) ) )
Output:
8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
Python
import doctest
import random
def flatten(lst):
"""
>>> flatten([[3,2],[1,2]])
[3, 2, 1, 2]
"""
return [i for sublst in lst for i in sublst]
def magic_shuffle(deck):
"""
>>> magic_shuffle([1,2,3,4])
[1, 3, 2, 4]
"""
half = len(deck) // 2
return flatten(zip(deck[:half], deck[half:]))
def after_how_many_is_equal(shuffle_type,start,end):
"""
>>> after_how_many_is_equal(magic_shuffle,[1,2,3,4],[1,2,3,4])
2
"""
start = shuffle_type(start)
counter = 1
while start != end:
start = shuffle_type(start)
counter += 1
return counter
def main():
doctest.testmod()
print("Length of the deck of cards | Perfect shuffles needed to obtain the same deck back")
for length in (8, 24, 52, 100, 1020, 1024, 10000):
deck = list(range(length))
shuffles_needed = after_how_many_is_equal(magic_shuffle,deck,deck)
print("{} | {}".format(length,shuffles_needed))
if __name__ == "__main__":
main()
More functional version of the same code:
"""
Brute force solution for the Perfect Shuffle problem.
See http://oeis.org/A002326 for possible improvements
"""
from functools import partial
from itertools import chain
from operator import eq
from typing import (Callable,
Iterable,
Iterator,
List,
TypeVar)
T = TypeVar('T')
def main():
print("Deck length | Shuffles ")
for length in (8, 24, 52, 100, 1020, 1024, 10000):
deck = list(range(length))
shuffles_needed = spin_number(deck, shuffle)
print(f"{length:<11} | {shuffles_needed}")
def shuffle(deck: List[T]) -> List[T]:
"""[1, 2, 3, 4] -> [1, 3, 2, 4]"""
half = len(deck) // 2
return list(chain.from_iterable(zip(deck[:half], deck[half:])))
def spin_number(source: T,
function: Callable[[T], T]) -> int:
"""
Applies given function to the source
until the result becomes equal to it,
returns the number of calls
"""
is_equal_source = partial(eq, source)
spins = repeat_call(function, source)
return next_index(is_equal_source,
spins,
start=1)
def repeat_call(function: Callable[[T], T],
value: T) -> Iterator[T]:
"""(f, x) -> f(x), f(f(x)), f(f(f(x))), ..."""
while True:
value = function(value)
yield value
def next_index(predicate: Callable[[T], bool],
iterable: Iterable[T],
start: int = 0) -> int:
"""
Returns index of the first element of the iterable
satisfying given condition
"""
for index, item in enumerate(iterable, start=start):
if predicate(item):
return index
if __name__ == "__main__":
main()
- Output:
Deck length | Shuffles 8 | 3 24 | 11 52 | 8 100 | 30 1020 | 1018 1024 | 10 10000 | 300
Reversed shuffle or just calculate how many shuffles are needed:
def mul_ord2(n):
# directly calculate how many shuffles are needed to restore
# initial order: 2^o mod(n-1) == 1
if n == 2: return 1
n,t,o = n-1,2,1
while t != 1:
t,o = (t*2)%n,o+1
return o
def shuffles(n):
a,c = list(range(n)), 0
b = a
while True:
# Reverse shuffle; a[i] can be taken as the current
# position of the card with value i. This is faster.
a = a[0:n:2] + a[1:n:2]
c += 1
if b == a: break
return c
for n in range(2, 10000, 2):
#print(n, mul_ord2(n))
print(n, shuffles(n))
Quackery
[ [] swap
times [ i^ join ] ] is deck ( n --> [ )
[ dup size 2 / split swap
witheach
[ swap i^ 2 * stuff ] ] is weave ( [ --> [ )
[ 0 swap
deck dup
[ rot 1+ unrot
weave 2dup = until ]
2drop ] is shuffles ( n --> n )
' [ 8 24 52 100 1020 1024 10000 ]
witheach
[ say "A deck of "
dup echo say " cards needs "
shuffles echo say " shuffles."
cr ]
- Output:
A deck of 8 cards needs 3 shuffles. A deck of 24 cards needs 11 shuffles. A deck of 52 cards needs 8 shuffles. A deck of 100 cards needs 30 shuffles. A deck of 1020 cards needs 1018 shuffles. A deck of 1024 cards needs 10 shuffles. A deck of 10000 cards needs 300 shuffles.
R
Matrix solution
wave.shuffle <- function(n) {
deck <- 1:n ## create the original deck
new.deck <- c(matrix(data = deck, ncol = 2, byrow = TRUE)) ## shuffle the deck once
counter <- 1 ## track the number of loops
## defining a loop that shuffles the new deck until identical with the original one
## and in the same time increses the counter with 1 per loop
while (!identical(deck, new.deck)) { ## logical condition
new.deck <- c(matrix(data = new.deck, ncol = 2, byrow = TRUE)) ## shuffle
counter <- counter + 1 ## add 1 to the number of loops
}
return(counter) ## final result - total number of loops until the condition is met
}
test.values <- c(8, 24, 52, 100, 1020, 1024, 10000) ## the set of the test values
test <- sapply(test.values, wave.shuffle) ## apply the wave.shuffle function on each element
names(test) <- test.values ## name the result
test ## print the result out
- Output:
> test 8 24 52 100 1020 1024 10000 3 11 8 30 1018 10 300
Sequence solution
The previous solution exploits R's matrix construction; This solution exploits its array indexing.
#A strict reading of the task description says that we need a function that does exactly one shuffle.
pShuffle <- function(deck)
{
n <- length(deck)#Assumed even (as in task description).
shuffled <- array(n)#Maybe not as general as it could be, but the task said to use whatever was convenient.
shuffled[seq(from = 1, to = n, by = 2)] <- deck[seq(from = 1, to = n/2, by = 1)]
shuffled[seq(from = 2, to = n, by = 2)] <- deck[seq(from = 1 + n/2, to = n, by = 1)]
shuffled
}
task2 <- function(deck)
{
shuffled <- deck
count <- 0
repeat
{
shuffled <- pShuffle(shuffled)
count <- count + 1
if(all(shuffled == deck)) break
}
cat("It takes", count, "shuffles of a deck of size", length(deck), "to return to the original deck.","\n")
invisible(count)#For the unit tests. The task wanted this printed so we only return it invisibly.
}
#Tests - All done in one line.
mapply(function(x, y) task2(1:x) == y, c(8, 24, 52, 100, 1020, 1024, 10000), c(3, 11, 8, 30, 1018, 10, 300))
- Output:
> mapply(function(x, y) task2(1:x) == y, c(8, 24, 52, 100, 1020, 1024, 10000), c(3, 11, 8, 30, 1018, 10, 300)) It takes 3 shuffles of a deck of size 8 to return to the original deck. It takes 11 shuffles of a deck of size 24 to return to the original deck. It takes 8 shuffles of a deck of size 52 to return to the original deck. It takes 30 shuffles of a deck of size 100 to return to the original deck. It takes 1018 shuffles of a deck of size 1020 to return to the original deck. It takes 10 shuffles of a deck of size 1024 to return to the original deck. It takes 300 shuffles of a deck of size 10000 to return to the original deck. [1] TRUE TRUE TRUE TRUE TRUE TRUE TRUE
Racket
#lang racket/base
(require racket/list)
(define (perfect-shuffle l)
(define-values (as bs) (split-at l (/ (length l) 2)))
(foldr (λ (a b d) (list* a b d)) null as bs))
(define (perfect-shuffles-needed n)
(define-values (_ rv)
(for/fold ((d (perfect-shuffle (range n))) (i 1))
((_ (in-naturals))
#:break (apply < d))
(values (perfect-shuffle d) (add1 i))))
rv)
(module+ test
(require rackunit)
(check-equal? (perfect-shuffle '(1 2 3 4)) '(1 3 2 4))
(define (test-perfect-shuffles-needed n e)
(define psn (perfect-shuffles-needed n))
(printf "Deck size:\t~a\tShuffles needed:\t~a\t(~a)~%" n psn e)
(check-equal? psn e))
(for-each test-perfect-shuffles-needed
'(8 24 52 100 1020 1024 10000)
'(3 11 8 30 1018 10 300)))
- Output:
Deck size: 8 Shuffles needed: 3 (3) Deck size: 24 Shuffles needed: 11 (11) Deck size: 52 Shuffles needed: 8 (8) Deck size: 100 Shuffles needed: 30 (30) Deck size: 1020 Shuffles needed: 1018 (1018) Deck size: 1024 Shuffles needed: 10 (10) Deck size: 10000 Shuffles needed: 300 (300)
Raku
(formerly Perl 6)
for 8, 24, 52, 100, 1020, 1024, 10000 -> $size {
my ($n, @deck) = 1, |^$size;
$n++ until [<] @deck = flat [Z] @deck.rotor: @deck/2;
printf "%5d cards: %4d\n", $size, $n;
}
- Output:
8 cards: 3 24 cards: 11 52 cards: 8 100 cards: 30 1020 cards: 1018 1024 cards: 10 10000 cards: 300
REXX
unoptimized
/*REXX program performs a "perfect shuffle" for a number of even numbered decks. */
parse arg X /*optional list of test cases from C.L.*/
if X='' then X=8 24 52 100 1020 1024 10000 /*Not specified? Then use the default.*/
w=length(word(X, words(X))) /*used for right─aligning the numbers. */
do j=1 for words(X); y=word(X,j) /*use numbers in the test suite (list).*/
do k=1 for y; @.k=k; end /*k*/ /*generate a deck to be used (shuffled)*/
do t=1 until eq(); call magic; end /*t*/ /*shuffle until before equals after.*/
say 'deck size:' right(y,w)"," right(t,w) 'perfect shuffles.'
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
eq: do ?=1 for y; if @.?\==? then return 0; end; return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
magic: z=0 /*set the Z pointer (used as index).*/
h=y%2 /*get the half─way (midpoint) pointer. */
do s=1 for h; z=z+1; h=h+1 /*traipse through the card deck pips. */
!.z=@.s; z=z+1 /*assign left half; then bump pointer. */
!.z=@.h /* " right " */
end /*s*/ /*perform a perfect shuffle of the deck*/
do r=1 for y; @.r=!.r; end /*re─assign to the original card deck. */
return
output (abbreviated) when using the default input:
deck size: 8, 3 perfect shuffles. deck size: 24, 11 perfect shuffles. deck size: 52, 8 perfect shuffles. deck size: 100, 30 perfect shuffles. deck size: 1020, 1018 perfect shuffles. deck size: 1024, 10 perfect shuffles. deck size: 10000, 300 perfect shuffles.
optimized
This REXX version takes advantage that the 1st and last cards of the deck don't change.
/*REXX program does a "perfect shuffle" for a number of even numbered decks. */
parse arg X /*optional list of test cases from C.L.*/
if X='' then X=8 24 52 100 1020 1024 10000 /*Not specified? Use default.*/
w=length(word(X, words(X))) /*used for right─aligning the numbers. */
do j=1 for words(X); y=word(X,j) /*use numbers in the test suite (list).*/
do k=1 for y; @.k=k; end /*generate a deck to be shuffled (used)*/
do t=1 until eq(); call magic; end /*shuffle until before equals after.*/
say 'deck size:' right(y,w)"," right(t,w) 'perfect shuffles.'
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
eq: do ?=1 for y; if @.?\==? then return 0; end; return 1
/*──────────────────────────────────────────────────────────────────────────────────────*/
magic: z=1; h=y%2 /*H is (half─way) pointer.*/
do L=3 by 2 for h-1; z=z+1; !.L=@.z; end /*assign left half of deck.*/
do R=2 by 2 for h-1; h=h+1; !.R=@.h; end /* " right " " " */
do a=2 for y-2; @.a=!.a; end /*re─assign──►original deck*/
return
output is the same as the 1st version.
Ruby
def perfect_shuffle(deck_size = 52)
deck = (1..deck_size).to_a
original = deck.dup
half = deck_size / 2
1.step do |i|
deck = deck.first(half).zip(deck.last(half)).flatten
return i if deck == original
end
end
[8, 24, 52, 100, 1020, 1024, 10000].each {|i| puts "Perfect shuffles required for deck size #{i}: #{perfect_shuffle(i)}"}
- Output:
Perfect shuffles required for deck size 8: 3 Perfect shuffles required for deck size 24: 11 Perfect shuffles required for deck size 52: 8 Perfect shuffles required for deck size 100: 30 Perfect shuffles required for deck size 1020: 1018 Perfect shuffles required for deck size 1024: 10 Perfect shuffles required for deck size 10000: 300
Rust
extern crate itertools;
fn shuffle<T>(mut deck: Vec<T>) -> Vec<T> {
let index = deck.len() / 2;
let right_half = deck.split_off(index);
itertools::interleave(deck, right_half).collect()
}
fn main() {
for &size in &[8, 24, 52, 100, 1020, 1024, 10_000] {
let original_deck: Vec<_> = (0..size).collect();
let mut deck = original_deck.clone();
let mut iterations = 0;
loop {
deck = shuffle(deck);
iterations += 1;
if deck == original_deck {
break;
}
}
println!("{: >5}: {: >4}", size, iterations);
}
}
- Output:
8: 3 24: 11 52: 8 100: 30 1020: 1018 1024: 10 10000: 300
Scala
Imperative, Quick, dirty and ugly
- Output:
Best seen running in your browser either by ScalaFiddle (ES aka JavaScript, non JVM) or Scastie (remote JVM).
object PerfectShuffle extends App {
private def sizes = Seq(8, 24, 52, 100, 1020, 1024, 10000)
private def perfectShuffle(size: Int): Int = {
require(size % 2 == 0, "Card deck must be even")
val (half, a) = (size / 2, Array.range(0, size))
val original = a.clone
var count = 1
while (true) {
val aa = a.clone
for (i <- 0 until half) {
a(2 * i) = aa(i)
a(2 * i + 1) = aa(i + half)
}
if (a.deep == original.deep) return count
count += 1
}
0
}
for (size <- sizes) println(f"$size%5d : ${perfectShuffle(size)}%5d")
}
Scilab
function New=PerfectShuffle(Nitems,Nturns)
if modulo(Nitems,2)==0 then
X=1:Nitems;
for c=1:Nturns
X=matrix(X,Nitems/2,2)';
X=X(:);
end
New=X';
end
endfunction
Result=[];
Q=[8, 24, 52, 100, 1020, 1024, 10000];
for n=Q
Same=0;
T=0;
Compare=[];
while ~Same
T=T+1;
R=PerfectShuffle(n,T);
Compare = find(R-(1:n));
if Compare == [] then
Same = 1;
end
end
Result=[Result;T];
end
disp([Q', Result])
- Output:
8. 3. 24. 11. 52. 8. 100. 30. 1020. 1018. 1024. 10. 10000. 300.
SETL
program faro_shuffle;
loop for test in [8, 24, 52, 100, 1020, 1024, 10000] do
print(lpad(str test, 5) + " cards: " + lpad(str cycle [1..test], 4));
end loop;
op cycle(l);
start := l;
loop until l = start do
l := shuffle l;
n +:= 1;
end loop;
return n;
end op;
op shuffle(l);
return [l(mapindex(i,#l)) : i in [1..#l]];
end op;
proc mapindex(i, size);
return if odd i then i div 2+1 else (i+size) div 2 end;
end proc;
end program;
- Output:
8 cards: 3 24 cards: 11 52 cards: 8 100 cards: 30 1020 cards: 1018 1024 cards: 10 10000 cards: 300
Sidef
func perfect_shuffle(deck) {
deck/2 -> zip.flat
}
[8, 24, 52, 100, 1020, 1024, 10000].each { |size|
var deck = @(1..size)
var shuffled = deck
var n = (1..Inf -> lazy.first {
(shuffled = perfect_shuffle(shuffled)) == deck
})
printf("%5d cards: %4d\n", size, n)
}
- Output:
8 cards: 3 24 cards: 11 52 cards: 8 100 cards: 30 1020 cards: 1018 1024 cards: 10 10000 cards: 300
Swift
func perfectShuffle<T>(_ arr: [T]) -> [T]? {
guard arr.count & 1 == 0 else {
return nil
}
let half = arr.count / 2
var res = [T]()
for i in 0..<half {
res.append(arr[i])
res.append(arr[i + half])
}
return res
}
let decks = [
Array(1...8),
Array(1...24),
Array(1...52),
Array(1...100),
Array(1...1020),
Array(1...1024),
Array(1...10000)
]
for deck in decks {
var shuffled = deck
var shuffles = 0
repeat {
shuffled = perfectShuffle(shuffled)!
shuffles += 1
} while shuffled != deck
print("Deck of \(shuffled.count) took \(shuffles) shuffles to get back to original order")
}
- Output:
Deck of 8 took 3 shuffles to get back to original order Deck of 24 took 11 shuffles to get back to original order Deck of 52 took 8 shuffles to get back to original order Deck of 100 took 30 shuffles to get back to original order Deck of 1020 took 1018 shuffles to get back to original order Deck of 1024 took 10 shuffles to get back to original order Deck of 10000 took 300 shuffles to get back to original order
Tcl
Using tcltest to include an executable test case ..
namespace eval shuffle {
proc perfect {deck} {
if {[llength $deck]%2} {
return -code error "Deck must be of even length!"
}
set split [expr {[llength $deck]/2}]
set top [lrange $deck 0 $split-1]
set btm [lrange $deck $split end]
foreach a $top b $btm {
lappend res $a $b
}
return $res
}
proc cycle_length {transform deck} {
set d $deck
while 1 {
set d [$transform $d]
incr i
if {$d eq $deck} {return $i}
}
return $i
}
proc range {a {b ""}} {
if {$b eq ""} {
set b $a; set a 0
}
set res {}
while {$a < $b} {
lappend res $a
incr a
}
return $res
}
}
set ::argv {}
package require tcltest
tcltest::test "Test perfect shuffle cycles" {} -body {
lmap size {8 24 52 100 1020 1024 10000} {
shuffle::cycle_length perfect [range $size]
}
} -result {3 11 8 30 1018 10 300}
UNIX Shell
function faro {
if (( $# % 2 )); then
printf >&2 'Can only shuffle an even number of elements!\n'
return 1
fi
typeset -i half=$(($#/2)) i
typeset argv=("$@")
for (( i=0; i<half; ++i )); do
printf '%s\n%s\n' "${argv[i${ZSH_VERSION:++1}]}" "${argv[i+half${ZSH_VERSION:++1}]}"
done
}
function count_faros {
typeset argv=("$@")
typeset -i count=0
argv=($(faro "${argv[@]}"))
(( count += 1 ))
while [[ "${argv[*]}" != "$*" ]]; do
argv=($(faro "${argv[@]}"))
(( count += 1 ))
done
printf '%d\n' "$count"
}
# Include time taken, which is combined from the three shells in the output below
printf '%s\t%s\t%s\n' Size Shuffles Seconds
for size in 8 24 52 100 1020 1024 10000; do
eval "array=({1..$size})"
start=$(date +%s)
count=$(count_faros "${array[@]}")
taken=$(( $(date +%s) - start ))
printf '%d\t%d\t%d\n' "$size" "$count" "$taken"
done
- Output:
Size Shuffles Seconds (Bash/Ksh/Zsh) 8 3 0/0/0 24 11 0/0/0 52 8 0/0/0 100 30 0/0/0 1020 1018 20/4/8 1024 10 0/0/0 10000 300 87/12/29
VBA
Option Explicit
Sub Main()
Dim T, Arr, X As Long, C As Long
Arr = Array(8, 24, 52, 100, 1020, 1024, 10000)
For X = LBound(Arr) To UBound(Arr)
C = 0
Call PerfectShuffle(T, CLng(Arr(X)), C)
Debug.Print Right(String(19, " ") & "For " & Arr(X) & " cards => ", 19) & C & " shuffles needed."
Erase T
Next
End Sub
Private Sub PerfectShuffle(tb, NbCards As Long, Count As Long)
Dim arr1, arr2, StrInit As String, StrTest As String
tb = CreateArray(1, NbCards)
StrInit = Join(tb, " ")
Do
Count = Count + 1
Call DivideArr(tb, arr1, arr2)
tb = RemakeArray(arr1, arr2)
StrTest = Join(tb, " ")
Loop While StrTest <> StrInit
End Sub
Private Function CreateArray(First As Long, Length As Long) As String()
Dim i As Long, T() As String, C As Long
If IsEven(Length) Then
ReDim T(Length - 1)
For i = First To First + Length - 1
T(C) = i
C = C + 1
Next i
CreateArray = T
End If
End Function
Private Sub DivideArr(A, B, C)
Dim i As Long
B = A
ReDim Preserve B(UBound(A) \ 2)
ReDim C(UBound(B))
For i = LBound(C) To UBound(C)
C(i) = A(i + UBound(B) + 1)
Next
End Sub
Private Function RemakeArray(A1, A2) As String()
Dim i As Long, T() As String, C As Long
ReDim T((UBound(A2) * 2) + 1)
For i = LBound(T) To UBound(T) - 1 Step 2
T(i) = A1(C)
T(i + 1) = A2(C)
C = C + 1
Next
RemakeArray = T
End Function
Private Function IsEven(Number As Long) As Boolean
IsEven = (Number Mod 2 = 0)
End Function
- Output:
For 8 cards => 3 shuffles needed. For 24 cards => 11 shuffles needed. For 52 cards => 8 shuffles needed. For 100 cards => 30 shuffles needed. For 1020 cards => 1018 shuffles needed. For 1024 cards => 10 shuffles needed. For 10000 cards => 300 shuffles needed.
Wren
import "./fmt" for Fmt
var areSame = Fn.new { |a, b|
for (i in 0...a.count) if (a[i] != b[i]) return false
return true
}
var perfectShuffle = Fn.new { |a|
var n = a.count
var b = List.filled(n, 0)
var hSize = (n/2).floor
for (i in 0...hSize) b[i * 2] = a[i]
var j = 1
for (i in hSize...n) {
b[j] = a[i]
j = j + 2
}
return b
}
var countShuffles = Fn.new { |a|
var n = a.count
if (n < 2 || n % 2 == 1) Fiber.abort("Array must be even-sized and non-empty.")
var b = a
var count = 0
while (true) {
var c = perfectShuffle.call(b)
count = count + 1
if (areSame.call(a, c)) return count
b = c
}
}
System.print("Deck size Num shuffles")
System.print("--------- ------------")
var sizes = [8, 24, 52, 100, 1020, 1024, 10000]
for (size in sizes) {
var a = List.filled(size, 0)
for (i in 1...size) a[i] = i
var count = countShuffles.call(a)
Fmt.print("$-9d $d", size, count)
}
- Output:
Deck size Num shuffles --------- ------------ 8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
XPL0
int Deck(10000), Deck0(10000);
int Cases, Count, Test, Size, I;
proc Shuffle; \Do perfect shuffle of Deck0 into Deck
int DeckLeft, DeckRight;
int I;
[DeckLeft:= Deck0;
DeckRight:= Deck0 + Size*4/2; \4 bytes per integer
for I:= 0 to Size-1 do
Deck(I):= if I&1 then DeckRight(I/2)
else DeckLeft(I/2);
];
[Cases:= [8, 24, 52, 100, 1020, 1024, 10000];
for Test:= 0 to 7-1 do
[Size:= Cases(Test);
for I:= 0 to Size-1 do Deck(I):= I;
Count:= 0;
repeat for I:= 0 to Size-1 do Deck0(I):= Deck(I);
Shuffle;
Count:= Count+1;
for I:= 0 to Size-1 do
if Deck(I) # I then I:= Size;
until I = Size; \equal starting configuration
IntOut(0, Size); ChOut(0, 9\tab\); IntOut(0, Count); CrLf(0);
];
]
- Output:
8 3 24 11 52 8 100 30 1020 1018 1024 10 10000 300
zkl
fcn perfectShuffle(numCards){
deck,shuffle,n,N:=numCards.pump(List),deck,0,numCards/2;
do{ shuffle=shuffle[0,N].zip(shuffle[N,*]).flatten(); n+=1 }
while(deck!=shuffle);
n
}
foreach n in (T(8,24,52,100,1020,1024,10000)){
println("%5d : %d".fmt(n,perfectShuffle(n)));
}
- Output:
8 : 3 24 : 11 52 : 8 100 : 30 1020 : 1018 1024 : 10 10000 : 300
- Programming Tasks
- Solutions by Programming Task
- 11l
- Action!
- Ada
- ALGOL 68
- APL
- Arturo
- AutoHotkey
- C
- C sharp
- C++
- Clojure
- Common Lisp
- D
- Delphi
- System.SysUtils
- Dyalect
- EasyLang
- EchoLisp
- Elixir
- F Sharp
- Factor
- Fortran
- FreeBASIC
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- Mathematica
- Wolfram Language
- MATLAB
- Modula-2
- Nim
- Oforth
- PARI/GP
- PARI/GP examples needing attention
- Examples needing attention
- Perl
- Phix
- Picat
- PicoLisp
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ruby
- Rust
- Scala
- Scilab
- SETL
- Sidef
- Swift
- Tcl
- UNIX Shell
- VBA
- Wren
- Wren-fmt
- XPL0
- Zkl