Category: other topics

配列のデータをシャッフル

カードゲームやビンゴマシンを作る際には、配列のデータをシャッフルするアルゴリズムが重要

1
2
3
4
5
6
7
8
    $sample_ary = array(1,2,3,4,5);
 
    shuffle($sample_ary);
 
// display result
    foreach ($sample_ary as $v){
    echo $v."\n";
    }

フィッシャー・イェーツのシャッフル

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<pre><?php
// mt_rand() array shuffle function
    function mt_shuffle(&$a){
        $a = array_values($a);
        for ($i = count($a) - 1; $i >= 1; $i--){
            $r = mt_rand(0, $i);
            list($a[$i], $a[$r]) = array($a[$r], $a[$i]);
        }
    }
 
// mt_shuffle() use example
    $sample_ary = array(1,2,3,4,5);
    mt_shuffle($sample_ary);
    foreach($sample_ary as $v){
    echo $v."\n";
    }

Mersenne Twister

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
53
54
<?php
    $MT_N = 624;
    $MT_M = 397;
    $MT_UPPER_MASK = 0x80000000;
    $MT_LOWER_MASK = 0x7fffffff;
    $mt = &#91;&#93;;
    $mti = $MT_N + 1;
 
    // initialize
    function my_mt_srand($seed){
        global $mt, $mti, $MT_N;
        $mt&#91;0&#93; = $seed & 0xfffffff;
        for ($mti = 1; $mti < $MT_N; $mti++){
            $mt&#91;$mti&#93; = (1812433253 * ($mt&#91;$mti-1&#93; ^ ($mt&#91;$mti-1&#93; >> 30)) + $mti);
            $mt[$mti] &= 0xfffffff;
        }
    }
    function my_mt_rand($min, $max){
        $range = $max - $min + 1;
        return (my_mt_genrand_int32() % $range) + $min;
    }
    function my_mt_genrand_int32() {
        global $MT_N, $MT_M, $mt, $mti;
        global $MT_UPPER_MASK, $MT_LOWER_MASK;
         
        static $mag01;
        $mag01 = array(0x0, 0x9908b0df);
        // table initialize
        if ($mti == $MT_N){
            if ($mti == $MT_N + 1) my_mt_srand(time());
            // remake table
            for ($kk = 0; $kk < $MT_N - $MT_M; $kk++){
                $y = ($mt&#91;$kk&#93;&$MT_UPPER_MASK)|($mt&#91;$kk+1&#93;&$MT_LOWER_MASK);
                $mt&#91;$kk&#93; = $mt&#91;$kk+($MT_M-$MT_N)&#93; ^ ($y >> 1) ^ $mag01[$y & 0x1];
            }
            $y = ($mt[$MT_N-1]&$MT_UPPER_MASK)|($mt[0]&$MT_LOWER_MASK);
            $mt[$MT_N-1] = $mt[$MT_M-1] ^ ($y >> 1) ^ $mag01[$y & 0x1];
            $mti = 0;
        }
        $y = $mt[$mti++];
        $y ^= ($y >> 11);
        $y ^= ($y << 7) & 0x9d2c5680;
        $y ^= ($y << 15) & 0xefc60000;
        $y ^= ($y >> 18);
        return $y;
    }
 
    my_mt_srand(time());
$list = array('●','▲','■','◯','△','□')
    for ($i = 0; $i < 256; $i++){
        $c = $list&#91;my_mt_rand(0, 5)&#93;;
        echo $c;
        if($i % 16 == 15) echo "<br>";
    }

linear congruential generators

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?php
// rand initial number(seed)
    $lc_seed = 1;
// random function
    fuction lc_rand() {
        global $lc_seed;
        $MASK = 0xffffffff;
        $lc_seed = (1103515245 * $lc_seed + 12345) & $MASK;
        return ($lc_seed / 65536) % 32768;
    }
// initialize random function
    function lc_srand($seed) {
        global $lc_seed;
        $lc_seed = $seed;
    }
// example
    lc_srand(time());
    $list = array('●','▲','■','◯','△','□');
    for ($i = 0; $i < 256; $i++){
        $c = $list&#91;lc_rand() % 6&#93;;
        echo $c;
        if ($i % 16 == 15) echo "<br>";
    }

パスワード生成ツール

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
<?php
// random password program
// character list for passwords
$PASSWORD_CHARS =
    'ABCDEFGHIJKLMNOPQRSTUVWXZ'.
    'abcdefghijklmnopqrstuvwxz'.
    '0123456789_-#!$';
 
// make password and character list
    function password_gen($length){
        global $PASSWORD_CHARS;
        $bytes = openssl_random_pseudo_bytes($length);
        $chars_len = strlen($PASSWORD_CHARS);
        $result = "";
        for ($i = 0; $i < $length; $i++){
            $r = ord(substr($bytes, $i, 1)) % $char_len;
            $result .= substr($PASSWROD_CHARS, $r, 1);
        }
        result $result;
    }
 
$res = "";
    $len  = intval(empty($_GET&#91;"len"&#93;) ? 12 : $_GET&#91;"len"&#93;);
    if ($len == 0) $len = 12;
    for ($i = 1; $i <= 30; $i++){
        $res .= password_gen($len)."\n";
    }
?>
<html><body bgcolor="#f0f0f0">
<form>
文字数:<input name="len" value="12">
 <input type="submit" value="生成">
</form>
パスワード候補:<br>
<textarea rows="20" cols="20"><?php echo $res ?></textarea>
</body></html>

擬似乱数

1
2
3
4
5
6
7
8
9
10
11
12
<html><body style="font-size:32px; line-height:32px;">
<?php
// set color
    $colors = array("red", "blue", "yellow", "green", "black");
// draw 16x16
    for ($i = 0; $i < 256; $i++){
        $r = rand(0, count($colors)-1);
        $c = $colors&#91;$r&#93;;
        echo "<span style='color:$c'>■</span>";
        if ($i % 16 == 15) echo "<br>";
    }
?></body></html>

usortで安定ソート

$data = [
    ['name'=>'Arai', 'score'=>30],
    ['name'=>'Inoue', 'score'=>40],
    ['name'=>'Utada', 'score'=>30],
    ['name'=>'Okuda', 'score'=>40],
    ['name'=>'Kato', 'score'=>23]
    ];

    // record
    for ($i = 0; $i < count($data); i++){
        $data[$i]["id"] = $i + 1;
    }
    usort($data, function($a, $b){
          if ($a['score'] == $b['score']){
          return ($a['id'] > $b['id']) ? 1 : -1;
          });
    foreach ($data as $u){
    echo $u['id'].":".$u['name'].":".$u['score']."\n";
    }

usort()関数

// setting data
$arr = [
    ['name']=>'Kan', 'point'=>4],
    ['name']=>'Kenji', 'point'=>5],
    ['name']=>'Akai', 'point'=>3],
    ['name']=>'Genta', 'point'=>4],
    ['name']=>'Shizuka', 'point'=>8],
    ];
    $point_cmp = function ($a, $b) {
        return ($a['point'] < $b['point']) ? -1 : 1;
    };

    usort($arr, $point_cmp);
    //result
    foreach ($arr as $u) {
    echo $u['name'].":".$u['point']."\n";
    }

クイックソート

// quick sort
    function quick_sort(&$arr){
        if (count($arr) < 2) return $arr;
        $left = $right = array();
        $pivot = array_shift($arr);
        foreach ($arr as $v) {
            if ($v < $pivot){
                $left[] = $v;
            } else {
                right[] = $v;
            }
        }
        quick_sort($left);
        quick_sort($right);
        $arr = array_merge($left, array($pivot), $right);
    }


    $arr = array(1,100,24,40,12,4);
    quick_sort($arr);
    echo implode(', ', $arr)."\n";

コムソート

 1 || $swap){
                if ($gap > 1) {
                    $gap = floor($gap / 1.25);
                    if ($gap == 9 || $gap == 10) $gap = 11;
                }
                $swap = false;
                $i = 0;
                while($i + $gap < size) {
                    if ($arr[$i] > $arr[$i + $gap]){
                        $tmp = $arr[$i];
                        $arr[$i] = $arr[$i + $gap];
                        $arr[$i + $gap] = $tmp;
                        $swap = true;
                    }
                    $i++;
                }
                
            }
        }
    }
    $arr = array(100, 3, 30, 20, 44, 32);
    comb_sort($arr);
    echo implode(", ", $arr)."\n"