我正在编写一个脚本来将任意数字均匀地$epi放入任意数量的 bin$dpi中。Epi 代表每英寸端数。dpi 表示每英寸的凹痕数。有3个要求：
- 如果可能，bin 编号应减少最小公因数
- 例如 6 dpi 中的 10 个 Epi 应由 3 dpi 中的 5 个 Epi 表示
- bin 人口应尽可能统一
- 例如 2-2-1 优于 3-1-1
- 短 bin 应均匀分布在 bin 阵列中
- 例如 1-0-1-0-1 优于 1-1-1-0-0
这就是我到目前为止所拥有的。它主要做我需要的，但是当space()方法运行时，如果它的foreach循环必须执行多次，$epi 的分布不均匀。
<?php
class ReedSubstitution{
public $epi;
public $dpi;
function substitute($e,$d){
$this->epi=is_numeric($e)?$e:0;
$this->dpi=is_numeric($d)?$d:0;
if(empty($this->epi)||empty($this->dpi)) throw new Exception('Both desired ends per unit and available dents per unit must be specified.');
if($this->epi%$this->dpi ==0) return array($this->epi/$this->dpi);//short circuit for easy case
$this->unfraction();//make equivalent integers if dpi or epi are fractional
$gcd= ($this->epi < $this->dpi) ? $this->euclid($this->epi,$this->dpi) : $this->euclid($this->dpi,$this->epi);
$e=$this->epi/$gcd;
$d=$this->dpi/$gcd;
$q=floor($e/$d);//count that every dent gets
$r=$e%$d;//extra to be spread out over array
$reed=array_fill(0,$d,$q);
$this->space($reed,$r);
return $reed;
}
protected function unfraction(){
$emult=1;
$dmult=1;
if($this->epi-intval($this->epi)){ //epi has a fractional component
list($tmp,$er)=explode('.',$this->epi);
$emult=pow(10,strlen($er));
}
if($this->dpi-intval($this->dpi)){//dpi has a fractional component
list($tmp,$dr)=explode('.',$this->dpi);
$dmult=pow(10,strlen($dr));
}
$mult=($emult>$dmult)?$emult:$dmult;
$this->epi*=$mult;
$this->dpi*=$mult;
}
/**
* @desc evenly distribute remaining ends over entirety of dents
* @param Array $reed, dents in one pattern repeat
* @param Integer $r, remaining ends to be distributed
*/
protected function space(&$reed,$r){
$c=count($reed);
$i=0;
$jump=($r < $c-$r) ? $r : $c-$r;//use the smallest jump possible to reduce the looping
do{
for($i; $i<$c; $i=$i+$jump, $r--){
if($r==0)break;
$reed[$i]++;
}
$i=array_search(min($reed),$reed);//begin next loop (if necessary) at position with fewest ends
}while($r>0);
}
/**
* @desc return greatest common divisor as determined by Euclid's algorithm
* @param integer $large
* @param integer $small
* @return integer
*/
protected function euclid($large, $small){
$modulus=$large%$small;
if($modulus==0) {
return $small;
} else if($modulus==1){
return 1;
} else {
return $this->euclid($small,$modulus);//recursion
}
}
}
?>
输出错误：
$r=new ReedSubstitution();
$arr=$r->substitute(9,28);
/* BAD DISTRIBUTION
Array
(
[0] => 1
[1] => 1
[2] => 1
[3] => 0
[4] => 0
[5] => 0
[6] => 0
[7] => 0
[8] => 0
[9] => 1
[10] => 1
[11] => 1
[12] => 0
[13] => 0
[14] => 0
[15] => 0
[16] => 0
[17] => 0
[18] => 1
[19] => 1
[20] => 0
[21] => 0
[22] => 0
[23] => 0
[24] => 0
[25] => 0
[26] => 0
[27] => 1
)
*/
上面的分布应该是什么样子：
/* GOOD DISTRIBUTION
Array
(
[0] => 1
[1] => 0
[2] => 0
[3] => 1
[4] => 0
[5] => 0
[6] => 1
[7] => 0
[8] => 0
[9] => 1
[10] => 0
[11] => 0
[12] => 1
[13] => 0
[14] => 0
[15] => 1
[16] => 0
[17] => 0
[18] => 1
[19] => 0
[20] => 0
[21] => 1
[22] => 0
[23] => 0
[24] => 1
[25] => 0
[26] => 0
[27] => 0
)
*/
如何修复该space()方法，以便需要多个循环的分箱将产生可接受的分布？