如何减少范围列表？

Question

给定一个范围列表，例如：1-3,5,6-4,31,9,19,10,25-20，我如何将其简化为1-6,9-10,19-25,31？

这是我到目前为止所做的，它看起来有点复杂，所以有没有更简单/更聪明的方法来做到这一点。

$in = '1-3,5,6-4,31,9,19,10,25-20';
// Explode the list in ranges
$rs = explode(',', $in);
$tmp = array();
// for each range of the list
foreach($rs as $r) {
    // find the start and end date of the range
    if (preg_match('/(\d+)-(\d+)/', $r, $m)) {
        $start = $m[1];
        $end = $m[2];
    } else {
        // If only one date
        $start = $end = $r;
    }
    // flag each date in an array
    foreach(range($start,$end) as $i) {
        $tmp[$i] = 1;
    }
}
$str = '';
$prev = 999;
// for each date of a month (1-31)
for($i=1; $i<32; $i++) {
    // is this date flaged ?
    if (isset($tmp[$i])) {
        // is output string empty ?
        if ($str == '') {
            $str = $i;
        } else {
            // if the previous date is less than the current minus 1
            if ($i-1 > $prev) {
                // build the new range
                $str .= '-'.$prev.','.$i;
            }
        }
        $prev = $i;
    }
}
// build the last range
if ($i-1 > $prev) {
    $str .= '-'.$prev;
}
echo "str=$str\n";

注意:它必须在php 5.1.6下运行(我不能升级)。

仅供参考:这些数字表示每月的天数，因此限制为1-31天。

编辑：

从给定的日期范围(1-3,6,7-8)，我想获得另一个列表(1-3,6-8)，其中所有的范围都被重新计算和排序。

Answer 1

也许不是最有效的，但对于您正在使用的有限范围的值，应该不会太差：

$in = '1-3,5,6-4,31,9,19,10,25-20';

$inSets = explode(',',$in);
$outSets = array();
foreach($inSets as $inSet) {
    list($start,$end) = explode('-',$inSet.'-'.$inSet);
    $outSets = array_merge($outSets,range($start,$end));
}
$outSets = array_unique($outSets);
sort($outSets);

$newSets = array();
$start = $outSets[0];
$end = -1;
foreach($outSets as $outSet) {
    if ($outSet == $end+1) {
        $end = $outSet;
    } else {
        if ($start == $end) {
            $newSets[] = $start;
        } elseif($end > 0) {
            $newSets[] = $start.'-'.$end;
        }
        $start = $end = $outSet;
    }
}
if ($start == $end) {
    $newSets[] = $start;
} else {
    $newSets[] = $start.'-'.$end;
}
var_dump($newSets);
echo '<br />';

Answer 2

你只需要搜索你的数据来得到你想要的。在分隔符上拆分输入，在本例中为'，‘。然后以某种方式对其进行排序，这使您可以从当前位置向左搜索。取你的第一个元素，检查它是否是一个范围，并使用这个范围中的最高数字( 1-3个范围中的3个，如果3是单个元素，则为3)以进行进一步的比较。然后取列表中的第二个元素，检查它是否是最后一个元素的直接后继元素。如果是，则将第一个和第二个元素/范围合并到一个新的范围。重复一遍。

编辑:我对PHP不太确定，但是正则表达式对于这个问题来说有点过分了。只要在你的分解数组中寻找一个'-‘，你就会知道它是一个范围。对exp进行排序。数组保护了你的回溯，也就是你用$prev做的事情。您还可以在'-‘上分解分解数组中的每个元素，并检查结果数组的大小是否大于1，以了解元素是否为范围。

Answer 3

从算法的角度来看这个问题，让我们考虑一下你对这个问题施加的限制。所有的数字都是从1到31。该列表是“范围”的集合，每个范围由两个数字(开始和结束)定义。没有关于start是否大于、小于或等于end的规则。

因为我们有一个任意大的范围列表，但有一个明确的排序/组织这些范围的方法，所以分而治之的策略可能会产生最好的复杂性。

首先，我输入了一个很长很仔细的解释，说明我是如何在这个算法中创建每个步骤的(划分部分，征服药剂，优化，等等)。然而，解释变得非常冗长。为了缩短它，这里是最终的答案：

<?php
   $ranges = "1-3,5,6-4,31,9,19,10,25-20";
   $range_array = explode(',', $ranges);
   $include = array();
   foreach($range_array as $range){
       list($start, $end) = explode('-', $range.'-'.$range); //"1-3-1-3" or "5-5"
       $include = array_merge($include, range($start, $end));
   }
   $include = array_unique($include);
   sort($include);
   $new_ranges = array();
   $start = $include[0];
   $count = $start;
   // And begin the simple conquer algorithm
   for( $i = 1; $i < count($include); $i++ ){
       if( $include[$i] != ($count++) ){
           if($start == $count-1){
               $new_ranges[] = $start;
           } else {
               $new_ranges[] = $start."-".$count-1;
           }
           $start = $include[$i];
           $count = $start;
       }
   }
   $new_ranges = implode(',', $new_ranges);
?>

这应该(理论上)适用于任意长度的正整数数组。负整数会出错，因为-是我们的范围分隔符。