shuffle

add a note User Contributed Notes

m227 at tlen dot pl
13-Oct-2006 06:22


here come my three pennies about permutations. I did function below to work with word anagrams, it works flawlessly, however may be seen as a slow one.



/** (c) on LGPL license 2006.10 michal@glebowski.pl */

function fact($int){

   if($int<2)return 1;

   for($f=2;$int-1>1;$f*=$int--);

   return $f;

}



/** @return string string $s with $n-th character cut */ 

function del($s, $n) {

    return substr($s, 0, $n).substr($s, $n+1);

}

/** 

 * @param $s string word to permute

 * @param $n int n-th permutation  

 * @return string n-th permutation (out of strlen(string)!)

 */  

function perm($s, $n = null) {



    if ($n === null) return perms($s);



    $r = '';

    $l = strlen($s);

    while ($l--) {

        $f = fact($l);

        $p = floor($n/$f);

        $r.= $s{$p};

        $s = del($s, $p);

        $n-= $p*$f;

    }

    $r.=$s;

    return $r;

}

/** @return array array of all permutations */

function perms($s) {

    $p = array();

    for ($i=0;$i<fact(strlen($s));$i++)    $p[] = perm($s, $i);

    return $p;

}

08-Jun-2006 05:53


Posted below is code that you would expect to work



<?php



$keys = shuffle(array_keys($arr));



foreach ($keys as $key) {



  $arr_elem = $arr[$key];

  // do what you want with the array element



}



?>



This in fact does not work because shuffle returns a boolean true or false. More accurate code using this method would be:



<?php



$keys = array_keys($arr);

shuffle($keys);



foreach ($keys as $key) {



  $arr_elem = $arr[$key];

  // do what you want with the array element



}



?>

bsl04 uark edu
07-Jun-2006 04:41


I spoke too soon. Other readers spotted than Benton's code was a little wrong. What a mess this thread is.



This stuff isn't PHP, but I believe it correctly implements Fisher-Yates. random(a, b) returns a number n such that a <= n <= b. The arrays start at 0. Hopefully this is enough to help someone who's trying to implement FY (in whatever language).



i = data_length;

if (i == 0) return;

while (i--)

{

    r = random(0, i);

    tmp = data[i];

    data[i] = data[r];

    data[r] = tmp;

}

alejandro dot garza at itesm dot mx
11-Mar-2006 12:47


This is taken from an O'Reilly Book and modified slightly to return all possible permutations of a 1D array:



<?php



# Modified from http://linuxalpha1.eicn.ch/OReilly_books/ books/webprog/pcook/ch04_26.htm 

# Takes a non-associatuve 1D (vector) array of items

#  and returns an array of arrays with each possible permutation

function array_2D_permute($items, $perms = array( )) {

static $permuted_array;

    if (empty($items)) { 

        $permuted_array[]=$perms;

        #print_r($new);

      #print join(' ', $perms) . "\n";

    }  else {

        for ($i = count($items) - 1; $i >= 0; --$i) {

             $newitems = $items;

             $newperms = $perms;

             list($foo) = array_splice($newitems, $i, 1);

             array_unshift($newperms, $foo);

             array_2D_permute($newitems, $newperms);

         }

         return $permuted_array;

    }

}



$arr=array("Architecture","Mexico","Periodicals","Test");

$result=array_2D_permute($arr);

print_r($result);

?>

09-Mar-2006 05:09


another way to shuffle an associative array:



$keys = shuffle(array_keys($arr));



foreach ($keys as $key)

{

  $arr_elem = $arr[$key];

  // do what you want with the array element

}

08-Mar-2006 08:20


my throw at associative shuffle:



$keys = array_keys($arr);

$seed = (float)microtime() * 1000000;



srand($seed);

shuffle($keys);



srand($seed);

shuffle($arr);



$arr = array_combine($keys, $arr);

bill at SWScripts dot com
23-Sep-2005 12:45


Just a quick note to let people know that shuffle() will work on multidimensional associative arrays provided that the first key is already numeric.



So this array can be shuffled without losing any of the secondary keys or their values:



$array[0]['color'], $array[0]['size'], $array[0]['fabric']

. . .

$array[50]['color'], $array[50]['size'], $array[50]['fabric']



I recently ran up against needing to randomize this array and tried shuffle even though it's not really for associative arrays.



Hope it helps somebody out there.

Markus of CodeWallah.Com
31-Aug-2005 01:55


Here's a pretty little function to shuffle an associative array, taking a bit different approach from the earlier entries. 



<?PHP

function ass_array_shuffle ($array) {

    while (count($array) > 0) {

        $val = array_rand($array);

        $new_arr[$val] = $array[$val];

        unset($array[$val]);

    }

    return $new_arr;

}

?>



In the function above, the original array is randomly scavenged upon until nothing is left of it. This removes the need for any temporary variables, or indeed for any superfluous tossing around of stuff.

anders dot carlsson at sfks dot se
05-Jul-2005 05:17


Vladimir's routine to sort an associated array is great, but one may want to add a clause to check that the array is not empty:



if (count($shuffle_me)>0) { code }



This is because array_rand does not like to pick zero entries out of an empty array (at least not in PHP 4.x).

skissane at iips dot mq dot edu dot au
06-Jun-2005 06:11


note that in PHP 5.0.4 (and assumably earlier versions as well), shuffle internally calls rand(), not mt_rand().



This was important because I was trying to use a fixed seed to get repeatable results, by calling mt_srand(). But of course that doesn't work, since shuffle uses rand() not mt_rand(). The solution is either to use srand() for seeding, or to write your own version of shuffle() using mt_rand(). (See examples which others have contributed; or, just have a look at ext/standard/array.c) mt_rand on many platforms gives better results than the builtin library anyway...



N.B. Obviously, the way the shuffle function is implemented may change without notice in future versions, including e.g. changing to use mt_rand instead.

berndt at www dot michael - berndt dot de
08-May-2005 03:18


randomize an assoziativ array with shuffle ()

http://www.michael-berndt.de/ie/tux/zufall_array_assoziativ.htm

berndt at michael - berndt dot de
17-Apr-2005 09:59


create secure passwords with shuffle()

http://www.michael-berndt.de/ie/tux/secure_password.htm

monte at ohrt dot com
22-Mar-2005 06:10


This is an attempt to get the Fisher Yates shuffle right, and as optimized as possible. The array items are stepped through from last to first, each being swapped with another between itself and the beginning of the array (N-1 shuffles required.) Using list() to swap array vars instead of a tmp var proved to be slightly slower. Testing for $i = $j decreases performance as the array size increases, so it was left out (elements are always swapped.)



function fisherYatesShuffle(&$items)

{

   for ($i = count($items) - 1; $i > 0; $i--)

   {

      $j = @mt_rand(0, $i);

      $tmp = $items[$i];

      $items[$i] = $items[$j];

      $items[$j] = $tmp;

   }

}

Vladimir Kornea of typetango.com
26-Oct-2004 05:06


shuffle() does not maintain key associations. This is how to shuffle an associative array without losing key associations:





<?php


function shuffle_me($shuffle_me) {


    $randomized_keys = array_rand($shuffle_me, count($shuffle_me));


    foreach($randomized_keys as $current_key) {


        $shuffled_me[$current_key] = $shuffle_me[$current_key];


    }


    return $shuffled_me;


}


?>





This is simpler than the other methods described here and it actually works.

al at giicorp dot com
21-Oct-2004 08:33


When shuffling large sets this got a faster response, since $array is always the same size, those extra millisecs counts.



function fisherYatesShuffle(&$array)

{

   $total = count($array);// <-- 

   for ($i = 0; $i<$total; $i++)

   {

         $j = @mt_rand(0, $i);

         $temp = $array[$i];

         $array[$i] = $array[$j];

         $array[$j] = $temp;

   }

}

Bjorn AT smokingmedia DOT com
23-Sep-2004 08:02


To shuffle an associated array and remain the association between keys and values, use this function:



<?php



$test_array = array("first" => 1,"second" => 2,"third" => 3,"fourth" => 4);



function shuffle_assoc($input_array){



   foreach($input_array as $key => $value){

      $temp_array[$value][key] = $key;

      }



   shuffle($input_array);



   foreach($input_array as $key => $value){

      $return_array[$temp_array[$value][key]] = $value;

      }



   return $return_array;

   }



echo "<pre>";

print_r(shuffle_assoc($test_array));

echo "</pre><hr />";



// this will output something like this:

/*

Array

(

    [fourth] => 4

    [second] => 2

    [third] => 3

    [first] => 1

)



*/

?>

bryan at mcnett dot org
20-Apr-2004 06:35


The technique described in the following article enables visiting each in a range of integers exactly once, but in perceptually random order. A reprint of this article appears in Graphics Gems:



http://www.mactech.com/articles/mactech/Vol.06/06.12/SafeDissolve/



It's possible to cheaply permute the order of integers so produced with XOR et al. This may enable random shuffling of arrays with less guarantee of true randomness, but more guarantee that the output looks different from the input, which is probably what you want.



The above technique belongs to the family of LFR (Linear Feedback Registers), which have a long history of providing "enough randomness" at very low cost.

Justin Knoll
16-Apr-2004 08:24


This code is very appealing in its simplicity and speed, but it's not a random shuffle:



<?php

function randomcmp($a, $b)

{

  return mt_rand(-1, 1);

}



function swapshuffle(&$array)

{

  srand((double) microtime() * 10000000);

  uksort($array, "randomcmp");

}

?>



This is because uksort calls the C function zend_qsort and this quicksorts the array using the provided comparision function. The pairs of indices selected are biased by the nature of the quicksort algorithm.



One effect is that an element in the middle of the array is heavily biased toward being "shuffled" to the middle. Elements on the edges are biased towards the edges; they're likely to switch edges, but unlikely to end up in the middle.

injunjoel
12-Mar-2004 11:27


Be aware that when shuffling an associative array your associative keys will be lost! example below:

<?php

echo "before shuffle\n";

$numbers = array('first'=>1,'second'=>2,'third'=>3,'fourth'=>4);

foreach($numbers as $key=>$value){

    echo "$key => $value\n";

}

echo "\nafter shuffle\n";

srand((float)microtime() * 1000000);

shuffle($numbers);



foreach($numbers as $key=>$value){

    echo "$key => $value\n";

}



?>

--output--

before shuffle

first => 1

second => 2

third => 3

fourth => 4



after shuffle

0 => 4

1 => 1

2 => 3

3 => 2

add a note

shuffle

说明