Perfect shuffle: Difference between revisions

=={{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===

<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.</lang>

{{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).

<lang Picat>main =>

N = 8,

println(1..N),

InOut = in, % in shuffling

Count = show_all_shuffles(N,InOut,true),

println(count=Count),

nl.</lang>

{{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).

<lang Picat>main =>

N = 11,

println(1..N),

InOut = out, % in/out shuffling

Count = show_all_shuffles(N,InOut,true),

println(count=Count),

nl.</lang>

{{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>