添加2个变化版本的费歇尔-耶茨-科诺斯无偏置洗牌算法,只包括索引或排除索引(类似PHP的伪代码)。
function shuffle_include( $a, $inc )
{
$N = count($inc);
while ( $N-- )
{
$perm = rnd( 0, $N );
$swap = $a[ $inc[$N] ];
$a[ $inc[$N] ] = a[ $inc[$perm] ];
$a[ $inc[$perm] ] = $swap;
}
return $a;
}
function shuffle_exclude( $a, $exc )
{
$inc = array();
$i=0; $j=0; $l = count($a); $le = count($exc)
while ($i < $l)
{
if ($j >= $le || $i<$exc[$j]) $inc[] = $i;
else $j++;
$i++;
}
$N = count($inc);
while ( $N-- )
{
$perm = rnd( 0, $N );
$swap = $a[ $inc[$N] ];
$a[ $inc[$N] ] = $a[ $inc[$perm] ];
$a[ $inc[$perm] ] = $swap;
}
return $a;
}
例子:
$a = array(1,2,3,4,5,6)
print_r( shuffle_include( $a, array(0,1,2) ) )
// sample output: [2,1,3,4,5,6] , only 0,1,2 indices are shuffled
print_r( shuffle_exclude( $a, array(0,1,2) ) )
// sample output: [1,2,3,6,5,4], all other indices are shuffled except 0,1,2
注意 PHP的shuffle函数本身使用了Fisher-Yates-Knuth洗牌算法的变体。
注意2 所有提供的洗牌算法(以及PHP的原始洗牌函数)都具有(平均)时间复杂度为$O(n)$(n=要洗牌的数组大小)。
有关shuffle
的其他变体,请参见:
- 从PHP数组中高效地选择n个随机元素(无需洗牌)