Contenitore uniformemente: spaziatura resto è irregolare
https://stackoverflow.com/questions/7811075
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto scrivendo uno script per uniformemente bin un numero $epi arbitraria in un numero arbitrario di bidoni $dpi. epi sta per Ends per pollice. dpi significa Dents per pollice. Ci sono 3 requisiti:
- numero di bin deve essere ridotta con il più basso fattore comune, se possibile
- es. 10 epi a 6 dpi dovrebbero essere rappresentati da 5 epi in 3 dpi
- popolazione bin deve essere il più uniforme possibile
- es. 2-2-1 è meglio di 3-1-1
- brevi bidoni deve essere distribuito in modo uniforme in tutta la matrice bin
- es. 1-0-1-0-1 è meglio di 1-1-1-0-0
Questo è quello che ho finora. Lo fa in gran parte quello che mi serve ma quando viene eseguito il metodo di space(), se il suo ciclo foreach deve eseguire più di una volta, la distribuzione di $ epi non è nemmeno.
<?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 uscita:
$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
)
*/
Che la distribuzione di cui sopra dovrebbe essere simile:
/* 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
)
*/
Come posso risolvere il metodo space() in modo che categorizzazione che richiede più di un loop produrrà una distribuzione accettabile?
Soluzione
Spero che questo potrebbe aiutare, o almeno si punto nella direzione giusta:
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;
}
}
Si può, tuttavia, non produce esattamente quello che ci si potrebbe aspettare:
Array
(
[0] => 2
[1] => 1
[2] => 2
[3] => 2
[4] => 1
[5] => 2
[6] => 1
[7] => 2
)
Anche se il risultato è una distribuzione uniforme.
P.S. Non ho ben capito vero sito web problema correlato si occupano di, ma spero afferrato il concetto di matematica destra.
Altri suggerimenti
Si può provare la seguente funzione per lo spazio.
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]++;
}
}
Ho appena provato con alcuni di ingresso e ha funzionato per me. Inoltre mi ha dato l'uscita corretta per l'esempio precedente hai dato.
Si può provare a utilizzare questa funzione e fatemi sapere se funziona per tutti i vostri input.
- EDIT -
Prova questo codice.
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]++;
}
}
Spero che funzioni. Non sono sicuro circa i risultati attesi gli altri ingressi che hai detto nel tuo commento. Quindi immagino che quanto segue sia corretta. Se mi sbaglio, quindi si prega di inviare i risultati attesi degli altri ingressi.
Saluti,
Wow, questo codice è orribile, imho :) ricorsione per trovare divisior comune, l'utilizzo folle di is_numeric e intval, uno exeption solitario architettura ecc .. La classe è troppo strano, avrei fatto questo come classe statica.
Onestamente, non ho avuto il problema di matematica su di esso, come tutto quello che ho trovato su bidoni e ammaccature è tessitura (io non sono un madrelingua così ho potuto aver perso qualcosa di ovvio), ma credo di aver capito le vostre esigenze ( se questo non è un problema di matematica rigorosa).
In ogni caso, ho ripulito tutto un po ', quindi vi posto il codice di classe completo, ma è possibile utilizzare lo spazio () separetely se non piace. Il mio algoritmo può essere ottimizzato un sacco (secondo ciclo può essere rimosso), ma sono troppo pigro per farlo.
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;
}
}
