Perfect shuffle: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Added C# implementation) |
m (→{{header|Wren}}: Minor tidy) |
||
| (48 intermediate revisions by 27 users not shown) | |||
Line 2:
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>
<!-- 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:
<big>
<!-- START OF DIAGRAM -->
::::: {| style="border-spacing:0.5em 0;border-collapse:separate;margin:0 1em;text-align:right"
|-
| <small>''original:''</small> ||
Line 52 ⟶ 55:
|}
<!-- END OF DIAGRAM -->
</big>
<p style="font-size:115%; margin:1em 0 0.5em 0">'''''The Task'''''</p>
Line 62 ⟶ 66:
<p style="font-size:115%; margin:1em 0 0.5em 0">'''''Test Cases'''''</p>
::::: {| class="wikitable"
|-
! input ''(deck size)'' !! output ''(number of shuffles required)''
Line 80 ⟶ 84:
| 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}}==
<
procedure perfect_shuffle is
Line 109 ⟶ 229:
put_line ("For" & size'img & " cards, there are "& count_shuffle (size / 2)'img & " shuffles needed.");
end loop;
end perfect_shuffle;</
{{out}}
<pre>
Line 122 ⟶ 242:
=={{header|ALGOL 68}}==
<
OP DECK = ( INT length )[]INT:
BEGIN
Line 179 ⟶ 299:
FOR l FROM LWB lengths TO UPB lengths DO
print( ( whole( lengths[ l ], -8 ) + ": " + whole( count shuffles( lengths[ l ] ), -6 ), newline ) )
OD</
{{out}}
<pre>
Line 190 ⟶ 310:
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}}==
<
n := cards.MaxIndex()/2, res := []
loop % n
res.push(cards[A_Index]), res.push(cards[round(A_Index + n)])
return res
}</
Examples:<
for each, val in test
{
Line 214 ⟶ 379:
}
MsgBox % result
return</
Outputs:<pre>8 3
24 11
Line 225 ⟶ 390:
=={{header|C}}==
<
#include <stdlib.h>
#include <stdio.h>
Line 335 ⟶ 500:
}
}
</syntaxhighlight>
{{out}}
Line 349 ⟶ 514:
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++}}==
<
#include <iostream>
#include <algorithm>
Line 391 ⟶ 602:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 401 ⟶ 612:
Cards count: 1024, shuffles required: 10.
Cards count: 10000, shuffles required: 300.
</pre>
=={{header|Clojure}}==
<
(let [half (split-at (/ (count deck) 2) deck)]
(interleave (first half) (last half))))
Line 461 ⟶ 626:
(inc (some identity (map-indexed (fn [i x] (when (predicate x) i)) trials)))))))
(map solve [8 24 52 100 1020 1024 10000])</
{{out}}
Line 475 ⟶ 640:
=={{header|Common Lisp}}==
<
(let* ((half (floor (length deck) 2))
(left (subseq deck 0 half))
Line 495 ⟶ 660:
(solve 1020)
(solve 1024)
(solve 10000)</
{{out}}
<pre> 8: 3
Line 507 ⟶ 672:
=={{header|D}}==
{{trans|Java}}
<
void main() {
Line 537 ⟶ 702:
assert(false, "How did this get here?");
}</
{{out}}
Line 547 ⟶ 712:
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}}==
<
;; shuffler : a permutation vector which interleaves both halves of deck
(define (make-shuffler n)
Line 569 ⟶ 927:
#:break (eqv? deck dock) ;; compare to first
1)))))
</syntaxhighlight>
{{out}}
<
map magic-shuffle '(8 24 52 100 1020 1024 10000))
→ ((8 . 3) (24 . 11) (52 . 8) (100 . 30) (1020 . 1018) (1024 . 10) (10000 . 300))
Line 585 ⟶ 943:
(oeis '(1 2 4 3 6 10 12 4))
→ Sequence A002326 found
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
<
def shuffle(n) do
start = Enum.to_list(1..n)
Line 612 ⟶ 970:
step = Perfect.shuffle(n)
IO.puts "#{n} : #{step}"
end)</
{{out}}
Line 626 ⟶ 984:
=={{header|F_Sharp|F#}}==
<
let perfectShuffle xs =
let h = (List.length xs) / 2
Line 642 ⟶ 1,000:
[ 8; 24; 52; 100; 1020; 1024; 10000 ] |> List.iter (fun n->n |> orderCount |> printfn "%d %d" n)
</syntaxhighlight>
{{out}}
Line 656 ⟶ 1,014:
=={{header|Factor}}==
<
sequences.merged ;
IN: rosetta-code.perfect-shuffle
Line 669 ⟶ 1,027:
"Deck size" "Number of shuffles required" "%-11s %-11s\n" printf
test-cases [ dup shuffle-count "%-11d %-11d\n" printf ] each</
{{out}}
<pre>
Line 680 ⟶ 1,038:
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}}==
<
import "fmt"
Line 741 ⟶ 1,250:
}
return
}</
{{out}}
<pre>Cards count: 8, shuffles required: 3
Line 752 ⟶ 1,261:
=={{header|Haskell}}==
<
shuffle lst = let (a,b) = splitAt (length lst `div` 2) lst
in foldMap (\(x,y) -> [x,y]) $ zip a b
Line 763 ⟶ 1,272:
report n = putStrLn ("deck of " ++ show n ++ " cards: "
++ show (countSuffles n) ++ " shuffles!")
countSuffles n = 1 + length (findCycle shuffle [1..n])</
{{out}}
Line 779 ⟶ 1,288:
The shuffle routine:
<
Here, the phrase ($ $ 0 1"_) would generate a sequence of 0s and 1s the same length as the argument sequence:
<
0 1 0 1 0 1</
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.
<
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 3 1 4 2 5</
And, that means it can also sort the original sequence into that order:
<
adbecf
shuf 'abcdefgh'
aebfcgdh</
And this will work for sequences of arbitrary length.
Line 809 ⟶ 1,318:
Meanwhile, the cycle length routine could look like this:
<
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.
Line 815 ⟶ 1,324:
So here is the task example (with most of the middle trimmed out to avoid crashing the rosettacode wiki implementation):
<
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│
Line 837 ⟶ 1,346:
├─────────┼─────────────────┤
│10000 │300 │
└─────────┴─────────────────┘</
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.
Line 843 ⟶ 1,352:
=={{header|Java}}==
{{works with|Java|8}}
<
import java.util.stream.IntStream;
Line 875 ⟶ 1,384:
}
}
}</
<pre> 8 : 3
Line 887 ⟶ 1,396:
=={{header|JavaScript}}==
===ES6===
<
'use strict';
Line 1,008 ⟶ 1,517:
.map(row => row.join(''))
.join('\n');
})();</
{{Out}}
Line 1,020 ⟶ 1,529:
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}}==
<
function perfect_shuffle(a::Array)::Array
Line 1,049 ⟶ 1,598:
count = count_perfect_shuffles(i)
@printf("%7i%7i\n", i, count)
end</
{{out}}
Line 1,063 ⟶ 1,612:
=={{header|Kotlin}}==
<
fun areSame(a: IntArray, b: IntArray): Boolean {
Line 1,103 ⟶ 1,652:
println("${"%-9d".format(size)} $count")
}
}</
{{out}}
Line 1,119 ⟶ 1,668:
=={{header|Lua}}==
<
function shuffle (cards)
local pile1, pile2 = {}, {}
Line 1,154 ⟶ 1,703:
local testCases = {8, 24, 52, 100, 1020, 1024, 10000}
print("Input", "Output")
for _, case in pairs(testCases) do print(case, countShuffles(case)) end</
{{out}}
<pre>Input Output
Line 1,165 ⟶ 1,714:
10000 300</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
shuffleCount[n_] := Block[{count=0}, NestWhile[shuffle, shuffle[Range[n]], (count++; OrderedQ[#] )&];count];
Map[shuffleCount, {8, 24, 52, 100, 1020, 1024, 10000}]</
{{out}}
<pre>{3, 11, 8, 30, 1018, 10, 300}</pre>
Line 1,174 ⟶ 1,723:
=={{header|MATLAB}}==
PerfectShuffle.m:
<
if mod(Nitems,2)==0 %only if even number
X=1:Nitems; %define deck
Line 1,182 ⟶ 1,731:
end
New=X; %result of multiple shufflings
end</
Main:
<
Q=[8, 24, 52, 100, 1020, 1024, 10000]; %queries
for n=Q %for each query
Line 1,197 ⟶ 1,746:
Result=[Result;T]; %collect results
end
disp([Q', Result])</
{{out}}
<pre> 8 3
Line 1,206 ⟶ 1,755:
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}}==
<
: nbShuffles(l) 1 l while( shuffle dup l <> ) [ 1 under+ ] drop ;</
{{out}}
Line 1,221 ⟶ 1,910:
{{improve|PARI/GP|The task description was updated; please update this solution accordingly and then remove this template.}}
<
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))</
{{out}}
<pre>%1 = [1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12,
Line 1,256 ⟶ 1,945:
=={{header|Perl}}==
<syntaxhighlight lang
use List::Util 'all';
sub perfect_shuffle (@deck) {
my $
map { @
}
for my $size (8, 24, 52, 100, 1020, 1024, 10000) {
my @shuffled = my @deck = 1..$size;
my
do { $n++; @shuffled = perfect_shuffle @shuffled }
until all { $shuffled[$_] == $deck[$_] } 0..$#shuffled;
printf "%5d cards: %4d\n", $size, $n;
}</
{{out}}
Line 1,284 ⟶ 1,972:
</pre>
=={{header|
<!--<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>
Line 1,315 ⟶ 2,008:
</pre>
=={{header|
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),
if Print then
println(1..N),
end,
Count = show_all_shuffles(N,InOut,Print),
println(count=Count),
nl,
fail,
%
% 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}}==
<
(mapcan '((B A) (list A B))
(cdr (nth Lst (/ (length Lst) 2)))
Line 1,359 ⟶ 2,208:
(until (= Lst (setq L (perfectShuffle L)))
(inc 'Cnt) )
(tab (5 6) N Cnt) ) )</
Output:
<pre> 8 3
Line 1,371 ⟶ 2,220:
=={{header|Python}}==
<
import doctest
import random
Line 1,417 ⟶ 2,266:
main()
</syntaxhighlight>
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:
<
# directly calculate how many shuffles are needed to restore
# initial order: 2^o mod(n-1) == 1
Line 1,443 ⟶ 2,370:
for n in range(2, 10000, 2):
#print(n, mul_ord2(n))
print(n, shuffles(n))</
=={{header|
<syntaxhighlight lang="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 ]</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
Line 1,463 ⟶ 2,423:
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}}==
<
(require racket/list)
Line 1,497 ⟶ 2,494:
(for-each test-perfect-shuffles-needed
'(8 24 52 100 1020 1024 10000)
'(3 11 8 30 1018 10 300)))</
{{out}}
Line 1,507 ⟶ 2,504:
Deck size: 1024 Shuffles needed: 10 (10)
Deck size: 10000 Shuffles needed: 300 (300)</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>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;
}</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|REXX}}==
===unoptimized===
<
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.*/
Line 1,534 ⟶ 2,550:
do r=1 for y; @.r=!.r; end /*re─assign to the original card deck. */
return</
'''output''' (abbreviated) when using the default input:
<pre>
Line 1,548 ⟶ 2,564:
===optimized===
This REXX version takes advantage that the 1<sup>st</sup> and last cards of the deck don't change.
<
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.*/
Line 1,568 ⟶ 2,584:
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 1<sup>st</sup> version.
<br><br>
Line 1,574 ⟶ 2,590:
=={{header|Ruby}}==
<
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
</syntaxhighlight>
{{out}}
<pre>
Perfect
Perfect
Perfect
Perfect
Perfect
Perfect
Perfect
</pre>
=={{header|Rust}}==
<
fn shuffle<T>(mut deck: Vec<T>) -> Vec<T> {
Line 1,618 ⟶ 2,637:
println!("{: >5}: {: >4}", size, iterations);
}
}</
{{out}}
<pre> 8: 3
Line 1,633 ⟶ 2,652:
{{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)].
<
private def sizes = Seq(8, 24, 52, 100, 1020, 1024, 10000)
Line 1,656 ⟶ 2,675:
for (size <- sizes) println(f"$size%5d : ${perfectShuffle(size)}%5d")
}</
=={{header|Scilab}}==
{{trans|MATLAB}}
<syntaxhighlight lang="text">function New=PerfectShuffle(Nitems,Nturns)
if modulo(Nitems,2)==0 then
X=1:Nitems;
Line 1,686 ⟶ 2,706:
Result=[Result;T];
end
disp([Q', Result])</
{{out}}
Line 1,697 ⟶ 2,717:
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}}
<
deck/2 -> zip.flat
}
Line 1,713 ⟶ 2,765:
printf("%5d cards: %4d\n", size, n)
}</
{{out}}
Line 1,725 ⟶ 2,777:
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}}==
Line 1,730 ⟶ 2,832:
Using <tt>tcltest</tt> to include an executable test case ..
<
proc perfect {deck} {
Line 1,775 ⟶ 2,877:
shuffle::cycle_length perfect [range $size]
}
} -result {3 11 8 30 1018 10 300}</
=={{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}}==
<
Sub Main()
Line 1,839 ⟶ 2,991:
Private Function IsEven(Number As Long) As Boolean
IsEven = (Number Mod 2 = 0)
End Function</
{{out}}
<pre> For 8 cards => 3 shuffles needed.
Line 1,849 ⟶ 3,001:
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}}==
<
deck,shuffle,n,N:=numCards.pump(List),deck,0,numCards/2;
do{ shuffle=shuffle[0,N].zip(shuffle[N,*]).flatten(); n+=1 }
Line 1,859 ⟶ 3,109:
foreach n in (T(8,24,52,100,1020,1024,10000)){
println("%5d : %d".fmt(n,perfectShuffle(n)));
}</
{{out}}
<pre>
| |||