Bin gleichmäßig: Der Restabstand ist ungleichmäßig
https://stackoverflow.com/questions/7811075
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich schreibe ein Skript, um eine willkürliche Nummer gleichmäßig abzusteuern $epi in eine willkürliche Anzahl von Behältern $dpi. EPI steht für Enden pro Zoll. DPI bedeutet Dellen pro Zoll. Es gibt 3 Anforderungen:
- Die Behälterzahl sollte nach Möglichkeit um den niedrigsten gemeinsamen Faktor reduziert werden
- ZB 10 EPI in 6 dpi sollte durch 5 epi in 3 dpi vertreten werden
- Die Population der Behälter sollte so einheitlich wie möglich sein
- ZB 2-2-1 ist besser als 3-1-1
- Kurze Behälter sollten gleichmäßig über das Behälter Array verteilt sein
- ZB 1-0-1-0-1 ist besser als 1-1-1-0-0
Das habe ich bisher. Es tut meistens das, was ich brauche aber wenn der space() Methode wird ausgeführt, wenn es ist foreach Schleife muss mehr als einmal ausführen, die Verteilung von $ epi ist noch nicht gerade.
<?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
}
}
}
?>
Schlechte Ausgabe:
$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
)
*/
Wie die obige Verteilung aussehen sollte:
/* 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
)
*/
Wie kann ich das beheben? space() Methode, damit Binning, das mehr als eine Schleife erfordert, eine akzeptable Verteilung erzeugt?
Lösung
Ich hoffe, das würde Ihnen helfen oder zumindest in die richtige Richtung weisen:
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;
}
}
Es kann jedoch nicht produzieren exakt Was Sie erwarten könnten:
Array
(
[0] => 2
[1] => 1
[2] => 2
[3] => 2
[4] => 1
[5] => 2
[6] => 1
[7] => 2
)
Obwohl das Ergebnis eine gleichmäßige Verteilung ist.
PS Ich habe das Problem mit dem realen Website nicht ganz verstanden, mit dem Sie es zu tun haben, aber ich hoffe, ich habe das Mathematikkonzept richtig verstanden.
Andere Tipps
Können Sie die folgende Funktion für den Raum ausprobieren?
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]++;
}
}
Ich habe es gerade mit einigen Eingaben versucht und es hat für mich funktioniert. Darüber hinaus gab es mir die richtige Ausgabe für das vorherige Beispiel, das Sie angegeben haben.
Können Sie versuchen, diese Funktion zu verwenden und mich wissen zu lassen, ob sie für alle Ihre Eingaben funktioniert?
-- BEARBEITEN --
Probieren Sie diesen Code aus.
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]++;
}
}
Ich hoffe das funktioniert. Ich bin mir nicht sicher über die erwarteten Ergebnisse der anderen Eingaben, die Sie in Ihrem Kommentar gesagt haben. Ich gehe also davon aus, dass das Folgende korrekt ist. Wenn ich falsch liege, veröffentlichen Sie bitte die erwarteten Ergebnisse der anderen Eingaben.
Grüße,
Wow, dieser Code ist schrecklich, IMHO :) Rekursion, um eine gemeinsame Divisior zu finden, wahnsinnige Verwendung von is_numerisch und intval, ein einsamer Auszug usw. Die Klassenarchitektur ist auch seltsam, ich hätte dies als statische Klasse getan.
Ehrlich gesagt, ich habe das mathematische Problem nicht bekommen, da alles, was ich über Behälter und Dellen gefunden habe Kein striktes Mathematikproblem).
Wie auch immer, ich habe es ein bisschen aufgeräumt, also poste ich einen vollständigen Klassencode, aber Sie können Space () getrennt verwenden, wenn Sie ihn nicht mögen. Mein Algorithmus kann viel optimiert werden (der zweite Zyklus kann entfernt werden), aber ich bin zu faul, um es zu tun.
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;
}
}
