Calculs de plages de nombres en PHP

Question

et tout d'abord, merci de prendre le temps de lire ma question. J'essaie d'écrire un script, et j'ai rencontré un problème que je trouve difficile à résoudre. Je travaille avec une paire de chiffres (par exemple, 1000 et 2000), et j'ai un tableau de paires de nombres:

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

Ce que je suis en train de trouver, est de savoir comment obtenir les fourchettes qui ne sont pas couverts par les paires de nombres, entre 1000 et 2000. Dans cet exemple, 1000-1100 est couvert par array (800, 1100), 1500-1600 est couvert par array (1500, 1600) et 1900-2000 est couvert par array (1900, 2100), qui me laisse avec 1101-1499 et 1599-1899 à gauche. J'espère que je suis assez clair. Ce que je me demande, c'est comment je pourrais faire revenir à PHP un tableau des plages non couvertes par la variable $ paires. Dans cet exemple, il retournera:

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

Avez-vous une idée de ce que serait la meilleure façon de faire cela?

Merci d'avance.

Answer 1

Eh bien, tout d'abord, vous devez définir le problème:

1. sont les couples triés?
2. Les paires se chevauchent-elles?
3. Vous voulez trouver les plages manquantes pour une plage particulière (cela semble être le cas)?

Si les paires ne sont pas classés, d'abord les trier:

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 sont autorisés plages qui se chevauchent, transformer la liste des paires à un ensemble sans chevauchement. Voici une suggestion sur la façon de le faire:

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

Maintenant, il ne devrait pas y avoir de paires qui se chevauchent de sorte que le problème devient un peu plus simple que vous avez aussi un tableau trié.

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

Espérons que ça aide.

Answer 2

je ferais quelque chose comme ça:

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 

Ceci est seulement une idée, mais voici le point: Considérez-vous un segment important (de 1000 à 2000) et petit. Vous voulez obtenir chaque segment du grand qui n'est pas couvert par le petit. Imaginez que vous avez un stylo!

Init le début. Itérer sur chaque "petit segment" que vous avez. Si vous êtes après (strictement) le début, alors il y a un "trou", donc vous devez mémoriser que de commencer au début du segment en cours.

Espérons que cela aide, et que c'est correct!

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

Trouver la différence de tableau

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

métadonnées sur les jeux que nous allons utiliser plus tard:

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

Sortie finale:

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

Résultat:

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

?>