Как уменьшить списки диапазонов?

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

Это должно (теоретически) работать с массивами произвольной длины для любых натуральных чисел. Отрицательные целые числа могут сработать, поскольку - является нашим разделителем для диапазона.

Answer 3

Вам просто нужно искать ваши данные, чтобы получить то, что вы хотите. Разделите ввод по разделителю, в вашем случае ','. Затем сортируйте это как-нибудь, это сохранит ваш поиск слева от текущей позиции. Возьмите первый элемент, проверьте, является ли он диапазоном, и используйте наибольшее число в этом диапазоне (3 из диапазона 1-3 или 3, если 3 - один элемент) для дальнейших сравнений. Затем возьмите 2-й элемент в вашем списке и проверьте, является ли он прямым наследником последнего элемента. Если да, объедините 1-й и 2-й элементы / диапазон в новый диапазон. Повторите.

Edit: я не уверен насчет PHP, но регулярное выражение немного излишне для этой проблемы. Просто посмотрите на «-» в вашем разобранном массиве, тогда вы знаете, что это диапазон. Сортировка опыта Массив позволяет вам вернуться назад, то, что вы делаете с $ prev. Вы также можете разбить каждый элемент в разобранном массиве на '-' и проверить, имеет ли результирующий массив размер> 1, чтобы узнать, является ли элемент диапазоном или нет.