Bin evenly: remainder spacing is uneven

Question

I'm writing a script to evenly bin an arbitrary number $epi into an arbitrary number of bins $dpi. epi stands for Ends per Inch. dpi means Dents per Inch. There are 3 requirements:

• bin number should be reduced by the lowest common factor if possible
  • e.g. 10 epi in 6 dpi should be represented by 5 epi in 3 dpi
• bin population should be as uniform as possible
  • e.g. 2-2-1 is better than 3-1-1
• short bins should be evenly distributed across the bin array
  • e.g. 1-0-1-0-1 is better than 1-1-1-0-0

This is what I have so far. It mostly does what I need but when the space() method is run, if its foreach loop has to execute more than once, the distribution of $epi is not even.

<?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
        }
    }
}
?>

Bad output:

$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
)
*/

What the above distribution should look like:

/* 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
)
*/

How can I fix the space() method so that binning requiring more than one loop will produce an acceptable distribution?

Answer 1

I hope this would help or at least point you to the right direction:

protected function space(&$reed, $r)
{
    $totalReeds = count($reed);

    $f = floor($r/$totalReeds);
    $d = ($r % $totalReeds) / $totalReeds;
    $c = 0;

    for ($i = 0; $i < $totalReeds; $i++)
    {
        $add = round($f + $d + $c);
        $reed[$i] += $add;
        $c = $c + $f + $d - $add;
    }
}

It can, however, produce not exactly what you might expect:

Array
(
    [0] => 2
    [1] => 1
    [2] => 2
    [3] => 2
    [4] => 1
    [5] => 2
    [6] => 1
    [7] => 2
)

Although the result is an even distribution.

P.S. I didn't quite understand real website related problem you dealing with, but I hope I grasped the math concept right.

Answer 2

Can you try the following function for space.

protected function space(&$reed, $r)
{
        $totalReeds = count ($reed);

        $postion = floor($totalReeds/$r);

        for ($i=0; $i<=$totalReeds; $i=$i+$postion, $r--) {
                if ($r <= 0) break;
                $reed[$i]++;
        }    
} 

I just tried with some input's and it worked for me. Moreover it gave me the correct output for the previous example you gave.

Can you try using this function and let me know if it works for all your input.

-- EDIT --

Try this code.

    protected function space(&$reed, $r)
    {
            $totalReeds = count ($reed);

            $postion = floor($totalReeds/$r);

            $postion = $postion == 1? 2 : $postion;

            for ($i=0; $i<=$totalReeds; $i=$i+$postion, $r--) {
                    if ($r <= 0) break;

                    if (isset($reed[$i])) $reed[$i]++;
            }    
    }     

I hope this works. I'm not sure about the expected results of the other inputs you said in your comment. So i assume that the following is correct. If i'm wrong, then please post the expected results of the other inputs.

http://ideone.com/L4fUv

Regards,

Answer 3

Wow, this code is horrible, imho :) Recursion to find common divisior, insane usage of is_numeric and intval, one lonely exeption etc.. Class architecture is strange too, I would have done this as static class.

Honestly, I didn't get the math problem about it as everything I found about bins and dents is weaving(I'm not a native speaker so I could have missed something obvious), but I think I understood your requirements (if this is not a strict math problem).

Anyway, I cleaned it up a bit, so I post complete class code, but you can use space() separetely if you don't like it. My algorithm can be optimized a lot(second cycle can be removed), but I'm too lazy to do it.

class ReedSubstitution {

    private $epi;
    private $dpi;

    public function substitute($e, $d) {
        $this->epi = floatval($e);
        $this->dpi = floatval($d);

        if (empty($this->epi) || empty($this->dpi)) {
            throw new Exception('Both desired ends per unit and available dents per unit must be specified.');
        }

        //make equivalent integers if dpi or epi are fractional
        $this->unfraction();

        if ($this->epi % $this->dpi == 0) {
            return array($this->epi / $this->dpi);
        }


        $gcd = $this->euclid($this->epi, $this->dpi);

        $e = $this->epi / $gcd;
        $d = $this->dpi / $gcd;

        $r = $e % $d; //extra to be spread out over array
        $q = ($e - $r) / $d; //count that every dent gets

        $reed = array_fill(0, $d, $q);
        $this->space($reed, $r);
        return $reed;
    }

    protected function unfraction() {
        //Find fraction start position
        $epi_fract_pos = strpos($this->epi, '.');
        $dpi_fract_pos = strpos($this->dpi, '.');
        //Find fraction length
        $epi_fract_len = $epi_fract_pos ? (strlen($this->epi) - $epi_fract_pos - 1) : 0;
        $dpi_fract_len = $dpi_fract_pos ? (strlen($this->dpi) - $dpi_fract_pos - 1) : 0;
        //Calculate max fraction length
        $fraction_len = max($epi_fract_len, $dpi_fract_len);
        //Unfraction variables
        $mult = pow(10, $fraction_len);
        $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);
        $base = $reed[0];
        for ($i = 0; $i < $r; $i++) {
            $reed[$i]++;
        }

        while ($reed[$c - 1] === $base) {
            $reed[$c] = $base;
            //Find the longest $base+1 array with least $base behind it
            $max_base_plus_size = -$c;
            $cur_base_plus_size = 0;
            $cur_base_plus_pos = array(NULL, NULL);
            $max_base_plus_pos = NULL;

            for ($i = 0; $i <= $c; $i++) {
                if ($reed[$i] != $base) {
                    if($cur_base_plus_pos[0]===NULL) {
                            $cur_base_plus_pos[0] = $i;
                    }
                    if ($reed[$i + 1] == $base) {
                        $cur_base_plus_pos[1]=$i;
                        if ($max_base_plus_size < $cur_base_plus_size) {
                            $max_base_plus_size = $cur_base_plus_size;
                            $max_base_plus_pos = $cur_base_plus_pos;
                        }
                        $cur_base_plus_size = 0;
                        $cur_base_plus_pos = array(NULL, NULL);
                    }
                    else {
                        $cur_base_plus_size++;
                    }
                } else {
                    $cur_base_plus_size--;
                    $cur_base_plus_pos[1] = $i - 1;
                }
            }
            $insert_pos=ceil(($max_base_plus_pos[1]+$max_base_plus_pos[0])/2);
            array_splice($reed,$insert_pos,0,$base);
        }
        array_splice($reed,$c);
        $reed=array_reverse($reed);//Optional, just to get the same output as you submitted
    }

    /**
     * @desc return greatest common divisor as determined by Euclid's algorithm
     * @param integer $x
     * @param integer $y
     * @return integer
     */
    protected function euclid($x, $y) {
        while ($x) {
            $temp = $x;
            $x = $y % $x;
            $y = $temp;
        }
        return $temp;
    }

}