当前位置： 文江博客话题详情

分箱均匀：余数间距不均匀

发布于 2024-12-10 20:52:33 字数 4008 浏览 2 评论 0原文

我正在编写一个脚本，将任意数量的 $epi 均匀地装入任意数量的容器 $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() 方法，以便需要多个循环的分箱将产生可接受的分布？

原文

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?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（3）

你的呼吸 2024-12-17 20:52:33

我希望这会有所帮助或至少为您指明正确的方向：

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

但是，它可能会产生不完全符合您预期的结果：

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

尽管结果是均匀分布。

PS我不太明白你处理的真正与网站相关的问题，但我希望我正确掌握了数学概念。

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.

回复 原文
杯别 2024-12-17 20:52:33

您可以尝试以下空间功能吗？

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]++;
        }    
}

我只是尝试了一些输入，它对我有用。此外，它为我提供了您前面给出的示例的正确输出。

您可以尝试使用此功能并让我知道它是否适用于您的所有输入。

-- 编辑 --

尝试这个代码。

    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]++;
            }    
    }

我希望这能起作用。我不确定您在评论中所说的其他意见的预期结果。所以我假设以下内容是正确的。如果我错了，请发布其他输入的预期结果。

http://ideone.com/L4fUv

问候，

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,

回复 原文
冬天旳寂寞 2024-12-17 20:52:33

哇，这段代码太可怕了，恕我直言：）递归查找公约数，is_numeric 和 intval 的疯狂用法，一个孤独的例外等等。类架构也很奇怪，我会把它作为静态类来完成。

老实说，我没有得到关于它的数学问题，因为我发现的关于垃圾箱和凹痕的所有东西都是编织的（我不是母语人士，所以我可能错过了一些明显的东西），但我想我理解你的要求（如果这是不是严格的数学问题）。

不管怎样，我清理了一下它，所以我发布了完整的类代码，但是如果你不喜欢它，你可以单独使用 space() 。我的算法可以优化很多（可以去掉第二个循环），但我懒得这么做。

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

}

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

}
回复 原文
~没有更多了~

关于作者

财迷小姐

暂无简介

文章
评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

α

文章 0 评论 0

メ斷腸人バ

文章 0 评论 0

人间不值得

文章 0 评论 0

所有深爱都是秘密

文章 0 评论 0

往事风中埋

文章 0 评论 0

别理我

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文