Алгоритм группировки последовательных строк
Мне действительно трудно разработать алгоритм для решения следующей проблемы:
Я буду принимать массив входов, как показано ниже:
$input = array('100', '101', '102', '110', '111', '112');
и вывод должен быть строкой, содержащей:
"100-102, 110-112".
В основном, что мне нужно сделать, это номера групп в последовательности, лайк От 100 до 102 и сформировать их в строку «100-102» поскольку все числа образуют последовательность. Но так как значение 110 не рядом с 102, ценности 110-112 должны быть сгруппированы, и будет сформирована строка «110-112».
Ввод не ограничиваясь номерами, однако, они струны. Так что я буду ожидать входных данных, таких как:
$input = array('N1', 'N2', 'N3', 'GX1', 'GX2', 'Z-3');
Следуя той же схеме, результат должен быть:
"N1-N3, GX1-GX3, Z-3"Мой псевдокод (я новичок), чтобы атаковать проблему по крайней мере цифры:
$sequenceArr = [];
$string = '';
foreach(...){
if(nextValue == prevValue+1){
$sequenceArr[] = nextValue;
}else{
//form the string from the sequenceArr
//if the preceeding string doesn't conform to the pattern anymore.
}
}
Проблема, с которой я столкнусь выше, заключается в том, что входные данные не отсортированы. Я мог бы их «отсортировать», но как насчет строк с символьными значениями в них? Я в некотором роде потерян, и я не думаю, что пойду куда-нибудь с этим решением.
* ОБНОВЛЕНО ДАЛЬШЕ ОПИСАНИЕ:
Это будет простой алгоритм группировки, только последнее число будет указывать на группировку,
AB-1-DF AB-2-DF и AB-3-DF будут НЕ быть сгруппированы в AB-1-DF — AB-3-DF. Это упрощает проблему, также префикс 0 не имеет значения, 001 и 002 можно сгруппировать как 1-2.
Простое правило в основном таково:
(character) - (number)
ABC - 1
Разница в характере означает совершенно другую вещь.
Решение
Вот то, что должно работать, если последовательные элементы расположены рядом друг с другом. И вы, вероятно, захотите написать свой are_sequential функция:
$input = ["1","2","4","6","7","8"];
$len = count($input);
$result = [];
function are_sequential($a,$b){
return $a + 1 == $b;
}
$i = 0;
while ($i < $len - 1){
$first = $input[$i];
$last = $input[$i];
$i++;
$sequenceLength = 1;
while (are_sequential($last, $input[$i])){
$last = $input[$i];
$sequenceLength++;
if ($i < $len - 1){
$i++;
}
}
if ($sequenceLength > 1){
$result[] = $first . "-" . $last;
} else {
$result[] = $first;
}
}
var_dump($result);
Выход:
array(3) {
[0]=>
string(3) "1-2"[1]=>
string(1) "4"[2]=>
string(3) "6-8"}
Другие решения
Сортируйте массив все чаще, используя стандартный предикат сравнения строк (в алфавитном порядке).
Затем сравните строки в парах.
Изолируйте префикс строки (все символы, кроме последнего) и сравните на равенство.
Если вы принимаете числовые суффиксы, состоящие из более чем одной цифры, вам необходимо выделить суффикс, преобразовать его в целое число и сравнить оставшийся префикс. (Регулярные выражения могут помочь вам.)
detector