CodeIQ MAGAZINECodeIQ MAGAZINE

トランプのカードを混ぜる仕組み(パーフェクトシャッフル)をプログラミングで調べてみよう #PHP

2014.03.12 Category:技術コラム Tag:

  • 16
  • このエントリーをはてなブックマークに追加
003アイキャッチ

トランプゲームを行う時、カードを混ぜる必要があります。このときの混ざる仕組みをプログラミングで調べてみます。身近なものが題材ですが、カードの枚数によって混ざり方が異なります。

子供やプログラム初心者に興味を持ってもらうには、こうした身近にあるものを題材にしてみると良いのではないでしょうか。
by レスキューワーク株式会社 水野史土

トランプのカードを混ぜる

トランプゲームを行う時、カードを混ぜる必要があります。カードを混ぜる方法にも、様々なものがありますが、ここでは、リフルシャッフルを取り上げます。
リフルシャッフルは、カード全体を半分に分けて、交互に一枚ずつ混ぜていく、というものです。

実際に手作業で行うと、一度に二、三枚が混ざる事もありますが、完全に一枚ずつ混ざる、という想定をします。完全に一枚ずつ混ざる混ぜ方をパーフェクトシャッフルと呼ぶこともあります。

今回の記事ではプログラムを書いて実際に混ざる様子を見る、をメインにしたいと思いますが、実は、カードの混ざり方には規則的な法則があります。群論という分野で様々な考察が行われているので、数理的な背景を知りたい方は調べてみてください。

プログラムを書いてみる

では実際にカードを混ぜるプログラムを書いてみましょう。

num = (int) $num;
            // 0からxまでの数を配置する(x: 枚数)
            for ($i=0;$inum;$i++) {
                array_push($this->card_list, $i);
            }
            // 最初の状態を出力
            $this->output();
        }

        function shuffle() {
            // カードの束を真ん中で2つに分ける
            $first = array_slice($this->card_list,0,ceil($this->num/2));
            $second = array_slice($this->card_list,ceil($this->num/2));
            // シャッフル後の束
            $output = array();
            while($first) {
                // 2つの束 $first, $second から一枚ずつ取り出し、
                // $output に一つずつ挿入する
                $temp_first = array_shift($first);
                $output[] = $temp_first;
                $temp_second = array_shift($second);
                if ($temp_second) {
                    $output[] = $temp_second;
                }
            }
            $this->card_list = $output;
        }

        function output() {
            // 配列を文字列に変換して出力
            echo implode(', ', $this->card_list);
        }
    }
?>





<?php
    if (2 = $_POST['card'] && 1 = $_POST['timeshuffle']) {
        $num_card = (int) $_POST['card'];
        $num_shuffle = (int) $_POST['timeshuffle'];
        $obj = new Cards($num_card);
        print '<hr>';
        for ($j=1;$jshuffle();
            $obj-&gt;output();
            echo ' (' . $j . '回目)<br>';
        }
    }
?&gt;
<form action='shuffle.php' method='post'>
カードの枚数(2-60):

シャッフル回数(1-60):


</form>

Cardsクラスには、カードを並べておく$card_listと枚数を記憶しておく$numプロパティがあります。

    protected $card_list = array();
    protected $num = 0;

コンストラクタでは、枚数分、数字を並べます。実際のトランプだと、それぞれのカードは4種のマーク(スペード/ハート/ダイヤ/クラブ)と数字で区別しますが、ここでは数字だけで区別します。52枚なら、0, 1, … 51の数字を使います。
またoutputメソッドを呼び出して、最初の並びを出力します。

    function __construct($num) {
        $this-&gt;num = (int) $num;
        // 0から$num-1までの数を配置する
        for ($i=0;$inum;$i++) {
            array_push($this-&gt;card_list, $i);
        }
        // 最初の状態を出力
        $this-&gt;output();
    }

shuffleメソッドは、カードを混ぜる処理です。ここでは愚直に、カード全体を2つに分ける($first,$secondに分ける)、分けた束から一枚ずつ取り出し、並べる($outputに挿入)をします。

    function shuffle() {
        // カードの束を真ん中で2つに分ける
        $first = array_slice($this-&gt;card_list,0,ceil($this-&gt;num/2));
        $second = array_slice($this-&gt;card_list,ceil($this-&gt;num/2));
        // シャッフル後の束
        $output = array();
        while($first) {
            // 2つの束 $first, $second から一枚ずつ取り出し、
            // $output に一つずつ挿入する
            $temp_first = array_shift($first);
            $output[] = $temp_first;
            $temp_second = array_shift($second);
            // 全体の枚数が奇数のとき、$firstが$secondより一枚多くなる(配列の要素数が一個多い)ので
            // $secondに要素が有るかどうかをチェックする
            if ($temp_second) {
                $output[] = $temp_second;
            }
        }
        // 並べ替えを反映する
        $this-&gt;card_list = $output;
    }

outputメソッドは、並べ替え結果を出力します。

    function output() {
        // 配列を文字列に変換して出力
        echo implode(', ', $this-&gt;card_list);
    }

ブラウザ上から、カードの枚数とシャッフルの回数を指定して実行できます。

まずは52枚で

カード枚数とシャッフル回数を指定できるようにプログラムしました。どの枚数から初めても良いのですが、まずはトランプの枚数と同じ、カード52枚で実行してみます。何回シャッフルしたら元に戻るか、予想してから読み進めてください。

以下に、各シャッフルでどのように混ざったか、を示します。(最初は上から順に0,1,2,…51とします)

0, 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 (最初)
0, 26, 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 (1回目)
0, 13, 26, 39, 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 (2回目)
0, 32, 13, 45, 26, 7, 39, 20, 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 (3回目)
0, 16, 32, 48, 13, 29, 45, 10, 26, 42, 7, 23, 39, 4, 20, 36, 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 (4回目)
0, 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, 1, 9, 17, 25, 33, 41, 49, 6, 14, 22, 30, 38, 46, 3, 11, 19, 27, 35, 43, 51 (5回目)
0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 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 (6回目)
0, 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, 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 (7回目)
0, 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 (8回目)

52枚の場合、8回のシャッフルで元に戻ることがわかりました。あなたの予想よりも多かったでしょうか、それとも少なかったでしょうか?

他の枚数でも試してみる

では、8回で戻るのは偶然なのでしょうか。枚数と関係があるのでしょうか。試してみましょう。

たとえば13枚で試してみた例です。13枚の場合は、12回シャッフルすると元に戻ります。

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 (最初)
0, 7, 1, 8, 2, 9, 3, 10, 4, 11, 5, 12, 6 (1回目)
0, 10, 7, 4, 1, 11, 8, 5, 2, 12, 9, 6, 3 (2回目)
0, 5, 10, 2, 7, 12, 4, 9, 1, 6, 11, 3, 8 (3回目)
0, 9, 5, 1, 10, 6, 2, 11, 7, 3, 12, 8, 4 (4回目)
0, 11, 9, 7, 5, 3, 1, 12, 10, 8, 6, 4, 2 (5回目)
0, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 (6回目)
0, 6, 12, 5, 11, 4, 10, 3, 9, 2, 8, 1, 7 (7回目)
0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, 10 (8回目)
0, 8, 3, 11, 6, 1, 9, 4, 12, 7, 2, 10, 5 (9回目)
0, 4, 8, 12, 3, 7, 11, 2, 6, 10, 1, 5, 9 (10回目)
0, 2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11 (11回目)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 (12回目)

枚数を変えてみると、元に戻るまでのシャッフル回数は異なることがわかりますね。また枚数が多いからといって、元に戻るまでのシャッフル回数が多いとも限らない、というのが面白いですね。

いろいろな枚数の場合で試してみましょう。トランプのシャッフルのような、身近なものでも、プログラミングの題材にすることができます。お子さん等に興味を持ってもらうには、こういった題材を取り上げてみるのも良いのではないでしょうか。

CodeIQコード銀行にあなたのコードを預けてみませんか?

  • CodeIQコード銀行ではあなたのコードを財産と考えます。
  • お預かりいただいたコードは、CodeIQコード銀行がしっかり評価し、フィードバックいたします。
  • 当コード銀行にお預けいただいたコードは、企業がみてスカウトをかける可能性があります。
  • 転職したい方や将来転職することを考えている方で、今の自分のスキルレベルを知りたい方はぜひ挑戦してみてください。
  • 企業からスカウトがきたら困る人は挑戦しないでください。

興味を持った方はこちらからチャレンジを!

  • 16
  • このエントリーをはてなブックマークに追加

■この記事を書いた人

avatar

レスキューワーク株式会社 水野史土

レスキューワーク株式会社(WordPressサイト/テーマ/プラグインの診断および障害復旧サービス)の代表取締役。。WordPressおよびNovius OS(FuelPHPベースのCMS)のコアコード貢献者。concrete5.orgのコミュニティリーダー。主な著書「徹底攻略 PHP5 技術者認定 [上級] 試験問題集」(共著)。

■関連記事

GUIでアプリケーションが作れるNovius OSで効率的な開発 #PHP... 「アプリケーション作成」ウィザードとは 「アプリケーション作成」ウィザードとは、Novius OSに標準同梱されているアプリケーションです。管理画面からアプリケーションの雛形を作ることができます。開発を効率化するツールとして役立ちます。 このウィザードを使ってアプリケーションの雛形を作ると、 ...
クイックソートとバブルソートを比較してみよう #PHP... クイックソートとバブルソート ソートの方法には様々な方法があります。よく知られているものには、クイックソートやバブルソートなどがあります。ほかにもソート方法がありますが、ここではこの2つを紹介します。尚、今回は要素の値は全て異なる前提とします。 バブルソート バブルソートは、一番小さい(or大...
Webサイト発注の指標にもなるconcrete5のポイント機能「Karma」とは? #concret... concrete5とは? concrete5とは、CMS(conctents management system)と呼ばれる、Webサイトをブラウザから更新できるようにするソフトウェアのことです。アメリカ、オレゴン州ポートランドで開発されていますが、英語だけでなく様々な言語に対応しています。日本語...
覚えておくと便利!min, max関数を使ってシンプルなコードを書く方法 #PHP... <Part1> min関数の活用法 min関数は、いくつかの値から最小のものを返す関数です。非常にシンプルですね。シンプルな関数ですが、使い方はいろいろあります。とり得る引数も様々です。 配列を引数にする場合 min関数は配列を引数にすることができます。この場合、配列の要素の中で最も小さい値を...
手軽に開発環境が作れるビルトインサーバーを使ってみよう #PHP... PHPの動作環境構築方法 PHPプログラムは、コマンドラインから実行することができます。しかし、たいていの場合は、ブラウザでアクセスし、実行することが多いでしょう。この場合、ウェブサーバーを用意してアクセスします。以下のように、いろいろな方法があります。 Apache等のウェブサーバーを起動す...
待ったなし!今すぐPHP5.3から移行しないと起こるかもしれないトラブルまとめ #PHP... まずは確認。PHP5.4で削除されるもの セーフモード、マジッククォート、register_globals、register_long_arraysが、PHP5.4で削除されています。これらはPHP5.3で非推奨となっていたものですが、PHP5.2以前ベースで開発していた等で使っている場合はコード...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ