代码之家 › 专栏 › 技术社区 › Toto

如何缩小范围列表?

algorithm php

Toto · 技术社区 · 14 年前

给出范围列表,即: 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) 重新计算和排序所有范围。

3 回复 | 直到 14 年前

Nifle Hassan Syed 14 年前

也许不是最有效的,但在你所使用的有限价值范围内也不应该太差:

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

DaClown 14 年前

你只需要搜索你的数据就可以得到你想要的。拆分分隔符上的输入,如果是“,”。然后以某种方式进行排序,这样可以确保从当前位置向左搜索时的安全性。取第一个元素,检查它是否是一个范围,并使用该范围内的最高数字(1-3范围中的3个,如果3是单个元素,则为3个)进行进一步比较。然后取列表中的第二个元素,检查它是否是最后一个元素的直接继承者。如果是,将第一个和第二个元素/范围组合到新范围。重复。

编辑:我不确定PHP,但是对于这个问题,正则表达式有点过分了。只需在你的爆炸阵列中寻找一个‘-’,你就知道它是一个范围。对exp.array进行排序可以保护您的回溯,保护您使用$prev所做的事情。您还可以在“-”上分解分解数组中的每个元素,并检查结果数组的大小是否为>1,以了解元素是否为范围。

Nifle Hassan Syed 14 年前

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

由于我们有一个任意大的范围列表,但是有一个确定的排序/组织方法,分而治之的策略可能产生最好的复杂性。

起初,我输入了一个非常长和仔细的解释,说明了我是如何在这个算法中创建每个步骤的(分割部分、征服药剂、优化等),但是解释却非常长。为了缩短时间,下面是最后的答案:

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

这应该(理论上)适用于任意长度的任意正整数数组。负整数会被绊倒,因为 - 是范围的分隔符。