Cálculos de rangos de números en PHP

Question

y antes que nada, gracias por tomarse el tiempo de leer mi pregunta.

Estoy tratando de escribir un guión y me he encontrado con un problema que me resulta difícil de resolver. Estoy trabajando con un par de números (por ejemplo, 1000 y 2000), y tengo una serie de pares de números:

$pairs = array(
    array(800, 1100),
    array(1500, 1600),
    array(1900, 2100)
)

Lo que estoy tratando de encontrar es cómo obtener los rangos no cubiertos por los pares de números, entre 1000 y 2000. En este ejemplo, 1000-1100 está cubierto por una matriz (800, 1100), 1500-1600 está cubierto by array (1500, 1600) y 1900-2000 está cubierto por array (1900, 2100), lo que me deja con 1101-1499 y 1599-1899 por cubrir. Espero ser lo suficientemente claro.

Lo que me pregunto es cómo haría que PHP me devolviera una matriz de los rangos no cubiertos por la variable $ pares. En este ejemplo, devolvería:

array(
    array(1101, 1499),
    array(1599, 1899)
)

¿Tienes alguna idea de cuál sería la mejor manera de hacer esto?

Gracias de antemano.

Answer 1

Bueno, primero debes definir el problema:

1. ¿Están ordenados los pares?
2. ¿Se superponen los pares?
3. ¿Desea encontrar los rangos faltantes para un rango particular (este parece ser el caso)?

Si los pares no están ordenados, primero ordénelos:

usort($pairs, 'cmp_pair');

function cmp_pair($a, $b) {
  if ($a[0] == $b[0]) {
    if ($a[1] == $b[1]) {
      return 0;
    } else {
      return $a[1] < $b[1] ? -1 : 1;
    }
  } else {
    return $a[0] < $b[0] ? -1 : 1;
  }
}

Si se permiten rangos superpuestos, transforme la lista de pares en un conjunto no superpuesto. Aquí hay una sugerencia sobre cómo hacerlo:

$prev = false;
$newpairs = array();
foreach ($pairs as $pair) {
  if ($prev) {
    // this also handles the case of merging two ranges
    // eg 100-199 with 200 to 250 to 100-250
    if ($prev[1] >= $pair[0]-1) {
      $prev = array($prev[0], max($prev[1], $pair[1]));
    } else {
      $newpairs[] = $prev;
    }
  }
  $prev = $pair;
}
$pairs = $newpairs;

Ahora no debería haber ningún par superpuesto, por lo que el problema se vuelve un poco más simple, ya que también tiene una matriz ordenada.

function missing($start, $end, $pairs) {
  $missing = array();
  $prev = false;
  foreach ($pairs as $pair) {
    // if the current pair starts above the end, we're done
    if ($pair[0] > $end) {
      break;
    }

    // we can ignore any pairs that end before the start
    if ($pair[1] < $start) {
      continue;
    }

    // if the pair encompasses the whole range, nothing is missing
    if ($pair[0] <= $start && $pair[1] >= $end) {
      break;
    }

    // if this is our first overlapping pair and it starts above
    // the start we can backfill the missing range
    if ($pair[0] > $start && !$missing) {
      $missing[] = array($start, $pair[0]);
    }

    // compare this pair to the previous one (if there is one) and
    // fill in the missing range
    if ($prev) {
      $missing[] = array($prev[1]+1, $pair[0]-1);
    }

    // set the previous
    $prev = $pair;
  }

  // if this never got set the whole range is missing
  if (!$prev) {
    $missing[] = array($start, $end);

  // if the last overlapping range ended before the end then
  // we are missing a range from the end of it to the end of
  // of the relevant range
  } else if ($prev[1] < $end) {
    $missing[] = array($prev[1]+1, $end);
  }

  // done!
  return $missing;
}

Espero que eso ayude.

Answer 2

Haría algo así:

begin = 1000
end   = 2000
uncovered = ()
foreach pairs as pair
  if (pair[0] > begin)
    push (uncovered, begin, pair[0])
    begin = pair[1]
  end if
end foreach

Esto es solo una idea, pero aquí está el punto: Considere que tiene un segmento grande (de 1000 a 2000) y uno pequeño. Desea obtener cada segmento del grande que no esté cubierto por el pequeño. ¡Imagina que tienes un bolígrafo!

Inicia el comienzo. Iterar en cada " segmento pequeño " tienes. Si está buscando (estrictamente) el comienzo, entonces hay un "agujero", por lo que debe memorizar desde el principio hasta el comienzo del segmento actual.

¡Espero que esto ayude, y que esto sea correcto!

Answer 3

// your original arrays of integers
$pairs = array(
    array(800, 1100),
    array(1500, 1600),
    array(1900, 2100)
);

// first, normalize the whole thing into a giant list of integers that
// are included in the array pairs, combine and sort numerically
$numbers_in_pairs = array();
foreach($pairs as $set) {
    $numbers_in_pairs = array_merge($numbers_in_pairs, range($set[0], $set[1]));
}
sort($numbers_in_pairs);

// find the min
$min = $numbers_in_pairs[0];

// find the max
$max = $numbers_in_pairs[count($numbers_in_pairs)-1];

Encuentra la diferencia de matriz

// create an array of all numbers inclusive between the min and max
$all_numbers = range($min, $max);

// the numbers NOT included in the set can be found by doing array_diff
// between the two arrays, we need to sort this to assure no errors when
// we iterate over it to get the maxes and mins
$not_in_set = array_diff($all_numbers, $numbers_in_pairs);
sort($not_in_set);

Metadatos sobre los conjuntos que usaremos más adelante:

// gather metadata about the numbers that are not inside the set
// $not_in_set_meta['min'] = lowest integer
// $not_in_set_meta['max'] = highest integer
// $not_in_set_meta['mins'] = min boundary integer
// $not_in_set_meta['maxes'] = max boundary integer
$not_in_set_meta = array();
for($i=0;$i<count($not_in_set);$i++) {
    if ($i == 0) {
        $not_in_set_meta['min'] = $not_in_set[$i];
        $not_in_set_meta['mins'][] = $not_in_set[$i];
    } else if ($i == count($not_in_set)-1 ) {
        $not_in_set_meta['max'] = $not_in_set[$i];
        $not_in_set_meta['maxes'][] = $not_in_set[$i];
    } else {
        // in the event that a number stands alone
        // that it can be BOTH the min and the max
        if (($not_in_set[$i+1] - $not_in_set[$i]) > 1) {
            $not_in_set_meta['maxes'][] = $not_in_set[$i];
        }
        if (($not_in_set[$i] - $not_in_set[$i-1]) > 1) {
            $not_in_set_meta['mins'][] = $not_in_set[$i];
        }
    }
}

Salida final:

// The final variable which we'll dump the ranges not covered into:
$non_sets = array();

while(count($not_in_set_meta['mins']) > 0 && count($not_in_set_meta['maxes'])) {
    $non_sets[] = array(array_shift($not_in_set_meta['mins']), 
                        array_shift($not_in_set_meta['maxes']));
}
// print it out:
print var_export($non_sets);

Resultado :

array (
  0 => 
  array (
    0 => 1101,
    1 => 1499,
  ),
  1 => 
  array (
    0 => 1601,
    1 => 1899,
  ),
)

?>