Perfect shuffle: Difference between revisions

{{trans|Python}}

 

[Int] r

L(sublst) lst

V deck = Array(0 .< length)

V shuffles_needed = after_how_many_is_equal(deck, deck)

 

{{out}}

1024 | 10

10000 | 300

</pre>

 

=={{header|Ada}}==

 

procedure perfect_shuffle is

put_line ("For" & size'img & " cards, there are "& count_shuffle (size / 2)'img & " shuffles needed.");

end loop;

{{out}}

<pre>

 

=={{header|ALGOL 68}}==

OP DECK = ( INT length )[]INT:

BEGIN

FOR l FROM LWB lengths TO UPB lengths DO

print( ( whole( lengths[ l ], -8 ) + ": " + whole( count shuffles( lengths[ l ] ), -6 ), newline ) )

{{out}}

<pre>

=={{header|APL}}==

{{works with|Dyalog APL}}

count ← {⍺←⍵ ⋄ ⍺≡r←⍺⍺ ⍵:1 ⋄ 1+⍺∇r}

{{out}}

<pre> 8 3

=={{header|Arturo}}==

 

deck: 1..deckSize

original: new deck

i: 1

while [true][

if deck = original -> return i

i: i+1

pad.right join @["Perfect shuffles required for deck size " to :string s ":"] 48

perfectShuffle s

 

{{out}}

 

=={{header|AutoHotkey}}==

n := cards.MaxIndex()/2, res := []

loop % n

res.push(cards[A_Index]), res.push(cards[round(A_Index + n)])

return res

for each, val in test

{

}

MsgBox % result

Outputs:<pre>8 3

24 11

=={{header|C}}==

 

#include <stdlib.h>

#include <stdio.h>

}

}

 

{{out}}

=={{header|C sharp}}==

{{works with|C sharp|6}}

using System.Collections.Generic;

using System.Linq;

}

{{out}}

<pre>

 

=={{header|C++}}==

#include <iostream>

#include <algorithm>

return 0;

}

{{out}}

<pre>

 

=={{header|Clojure}}==

(let [half (split-at (/ (count deck) 2) deck)]

(interleave (first half) (last half))))

(inc (some identity (map-indexed (fn [i x] (when (predicate x) i)) trials)))))))

 

 

{{out}}

 

=={{header|Common Lisp}}==

(let* ((half (floor (length deck) 2))

(left (subseq deck 0 half))

(solve 1020)

(solve 1024)

{{out}}

<pre> 8: 3

=={{header|D}}==

{{trans|Java}}

 

void main() {

 

assert(false, "How did this get here?");

 

{{out}}

{{libheader| System.SysUtils}}

{{Trans|Go}}

program Perfect_shuffle;

 

end;

readln;

 

=={{header|Dyalect}}==

{{trans|C#}}

 

}

var (t, l, r) = (0, 0, half)

while l < half {

result[t] = arr[l]

result

}

func arrayEqual(xs, ys) {

return false

}

if xs[i] != ys[i] {

return false

return true

}

func shuffleThrough(original) {

while true {

copy = shuffle(copy)

}

}

for input in yields { 8, 24, 52, 100, 1020, 1024, 10000} {

var numbers = [1..input]

 

{{out}}

1024 cards: 10

10000 cards: 300</pre>

 

=={{header|EchoLisp}}==

;; shuffler : a permutation vector which interleaves both halves of deck

(define (make-shuffler n)

#:break (eqv? deck dock) ;; compare to first

1)))))

 

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

(oeis '(1 2 4 3 6 10 12 4))

→ Sequence A002326 found

 

=={{header|Elixir}}==

{{trans|Ruby}}

def shuffle(n) do

start = Enum.to_list(1..n)

step = Perfect.shuffle(n)

IO.puts "#{n} : #{step}"

 

{{out}}

 

=={{header|F_Sharp|F#}}==

let perfectShuffle xs =

let h = (List.length xs) / 2

 

[ 8; 24; 52; 100; 1020; 1024; 10000 ] |> List.iter (fun n->n |> orderCount |> printfn "%d %d" n)

 

{{out}}

 

=={{header|Factor}}==

sequences.merged ;

IN: rosetta-code.perfect-shuffle

 

"Deck size" "Number of shuffles required" "%-11s %-11s\n" printf

{{out}}

<pre>

 

=={{header|Fortran}}==

IMPLICIT NONE

 

WRITE(*,'(I17, A, I35)') DECK_SIZES(I), " | ", COUNTER

END DO

<pre>

input (deck size) | output (number of shuffles required)

 

=={{header|FreeBASIC}}==

'tests if a deck is in order

for i as uinteger = lbound(d) to ubound(d)-1

for i = 1 to 7

print tests(i);" cards require "; shufs_needed(tests(i)); " shuffles."

{{out}}<pre>

8 cards require 3 shuffles.

 

=={{header|Go}}==

 

import "fmt"

}

return

{{out}}

<pre>Cards count: 8, shuffles required: 3

 

=={{header|Haskell}}==

shuffle lst = let (a,b) = splitAt (length lst `div` 2) lst

in foldMap (\(x,y) -> [x,y]) $ zip a b

report n = putStrLn ("deck of " ++ show n ++ " cards: "

++ show (countSuffles n) ++ " shuffles!")

 

{{out}}

The shuffle routine:

 

 

Here, the phrase ($ $ 0 1"_) would generate a sequence of 0s and 1s the same length as the argument sequence:

 

 

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.

 

 

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

 

 

And, that means it can also sort the original sequence into that order:

 

adbecf

shuf 'abcdefgh'

 

And this will work for sequences of arbitrary length.

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.

So here is the task example (with most of the middle trimmed out to avoid crashing the rosettacode wiki implementation):

 

 

Task example:

 

┌─────────┬─────────────────┐

│deck size│required shuffles│

├─────────┼─────────────────┤

│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.

=={{header|Java}}==

{{works with|Java|8}}

import java.util.stream.IntStream;

 

}

}

 

<pre> 8 : 3

=={{header|JavaScript}}==

===ES6===

'use strict';

 

.map(row => row.join(''))

.join('\n');

 

{{Out}}

 

A small point of interest in the following is the `recurrence` function as it is generic.

. as $a

| if (length % 2) == 1 then "cannot perform perfect shuffle on odd-length array" | error

 

(8, 24, 52, 100, 1020, 1024, 10000, 100000)

{{out}}

<pre>

 

=={{header|Julia}}==

 

function perfect_shuffle(a::Array)::Array

count = count_perfect_shuffles(i)

@printf("%7i%7i\n", i, count)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun areSame(a: IntArray, b: IntArray): Boolean {

println("${"%-9d".format(size)} $count")

}

 

{{out}}

 

=={{header|Lua}}==

function shuffle (cards)

local pile1, pile2 = {}, {}

local testCases = {8, 24, 52, 100, 1020, 1024, 10000}

print("Input", "Output")

{{out}}

<pre>Input Output

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

shuffleCount[n_] := Block[{count=0}, NestWhile[shuffle, shuffle[Range[n]], (count++; OrderedQ[#] )&];count];

{{out}}

<pre>{3, 11, 8, 30, 1018, 10, 300}</pre>

=={{header|MATLAB}}==

PerfectShuffle.m:

if mod(Nitems,2)==0 %only if even number

X=1:Nitems; %define deck

end

New=X; %result of multiple shufflings

 

Main:

Q=[8, 24, 52, 100, 1020, 1024, 10000]; %queries

for n=Q %for each query

Result=[Result;T]; %collect results

end

{{out}}

<pre> 8 3

=={{header|Modula-2}}==

{{trans|C}}

FROM FormatString IMPORT FormatString;

FROM Storage IMPORT ALLOCATE,DEALLOCATE;

 

ReadChar

{{out}}

<pre>8: 3

 

=={{header|Nim}}==

 

proc newValList(size: Positive): seq[int] =

if valList == initList:

break

 

 

=={{header|Oforth}}==

 

 

{{out}}

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

{{out}}

<pre>%1 = [1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12,

=={{header|Perl}}==

 

 

}

 

for my $size (8, 24, 52, 100, 1020, 1024, 10000) {

until all { $shuffled[$_] == $deck[$_] } 0..$#shuffled;

printf "%5d cards: %4d\n", $size, $n;

 

{{out}}

 

=={{header|Phix}}==

{{out}}

<pre>

10000 cards: 300

</pre>

 

=={{header|PicoLisp}}==

(mapcan '((B A) (list A B))

(cdr (nth Lst (/ (length Lst) 2)))

(until (= Lst (setq L (perfectShuffle L)))

(inc 'Cnt) )

Output:

<pre> 8 3

=={{header|Python}}==

 

import doctest

import random

main()

 

More functional version of the same code:

"""

Brute force solution for the Perfect Shuffle problem.

if __name__ == "__main__":

main()

{{Out}}

<pre>Deck length | Shuffles

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

for n in range(2, 10000, 2):

#print(n, mul_ord2(n))

 

=={{header|Quackery}}==

 

times [ i^ join ] ] is deck ( n --> [ )

 

dup echo say " cards needs "

shuffles echo say " shuffles."

 

{{Out}}

=={{header|R}}==

===Matrix solution===

deck <- 1:n ## create the original deck

new.deck <- c(matrix(data = deck, ncol = 2, byrow = TRUE)) ## shuffle the deck once

test <- sapply(test.values, wave.shuffle) ## apply the wave.shuffle function on each element

names(test) <- test.values ## name the result

{{out}}

<pre>> test

===Sequence solution===

The previous solution exploits R's matrix construction; This solution exploits its array indexing.

{

}

 

{

repeat

{

}

invisible(count)#For the unit tests. The task wanted this printed so we only return it invisibly.

}

 

#Tests - All done in one line.

{{out}}

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.

 

=={{header|Racket}}==

(require racket/list)

 

(for-each test-perfect-shuffles-needed

'(8 24 52 100 1020 1024 10000)

 

{{out}}

=={{header|Raku}}==

(formerly Perl 6)

printf "%5d cards: %4d\n", $size, $n;

 

{{out}}

=={{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.*/

 

do r=1 for y; @.r=!.r; end /*re─assign to the original card deck. */

'''output''' &nbsp; (abbreviated) &nbsp; when using the default input:

<pre>

===optimized===

This REXX version takes advantage that the 1^st 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.*/

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*/

'''output''' &nbsp; is the same as the 1^st version.

<br><br>

=={{header|Ruby}}==

 

deck = (1..deck_size).to_a

original = deck.dup

 

[8, 24, 52, 100, 1020, 1024, 10000].each {|i| puts "Perfect shuffles required for deck size #{i}: #{perfect_shuffle(i)}"}

 

{{out}}

 

=={{header|Rust}}==

 

fn shuffle<T>(mut deck: Vec<T>) -> Vec<T> {

println!("{: >5}: {: >4}", size, iterations);

}

{{out}}

<pre> 8: 3

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

 

for (size <- sizes) println(f"$size%5d : ${perfectShuffle(size)}%5d")

 

 

=={{header|Scilab}}==

{{trans|MATLAB}}

if modulo(Nitems,2)==0 then

X=1:Nitems;

Result=[Result;T];

end

 

{{out}}

1024. 10.

10000. 300.</pre>

 

=={{header|Sidef}}==

{{trans|Perl}}

deck/2 -> zip.flat

}

 

printf("%5d cards: %4d\n", size, n)

 

{{out}}

=={{header|Swift}}==

 

guard arr.count & 1 == 0 else {

return nil

 

print("Deck of \(shuffled.count) took \(shuffles) shuffles to get back to original order")

 

{{out}}

Using <tt>tcltest</tt> to include an executable test case ..

 

 

proc perfect {deck} {

shuffle::cycle_length perfect [range $size]

}

 

=={{header|VBA}}==

 

Sub Main()

Private Function IsEven(Number As Long) As Boolean

IsEven = (Number Mod 2 = 0)

{{out}}

<pre> For 8 cards => 3 shuffles needed.

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

 

var areSame = Fn.new { |a, b|

var count = countShuffles.call(a)

Fmt.print("$-9d $d", size, count)

 

{{out}}

 

=={{header|XPL0}}==

int Cases, Count, Test, Size, I;

 

IntOut(0, Size); ChOut(0, 9\tab\); IntOut(0, Count); CrLf(0);

];

 

{{out}}

 

=={{header|zkl}}==

deck,shuffle,n,N:=numCards.pump(List),deck,0,numCards/2;

do{ shuffle=shuffle[0,N].zip(shuffle[N,*]).flatten(); n+=1 }

foreach n in (T(8,24,52,100,1020,1024,10000)){

println("%5d : %d".fmt(n,perfectShuffle(n)));

{{out}}

<pre>