用于分组顺序字符串的算法

Question

I'm really having a hard time devising an algorithm to solve the following problem :

I will be accepting an array of inputs like below :

$input = array('100', '101', '102', '110', '111', '112');

and the output should be a string containing :

"100-102, 110-112".

Basically what I need to do is to group numbers in sequence, like 100 to 102 and form them in a string "100-102" since all numbers form a sequence. But since the value 110 is not next to 102, values 110 to 112 should be grouped and the string "110-112" will be formed.

Input is not limited to numbers however, they are strings. So I will be expecting inputs like:

$input = array('N1', 'N2', 'N3', 'GX1', 'GX2', 'Z-3');

Following the same pattern, the output should be:

"N1-N3, GX1-GX3, Z-3"

My pseudo-code (i'm a newbie) to attack the problem for the numbers atleast is:

$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.
   }
}

The problem I think I will be facing above is if the inputs are not sorted.. I could "sort" them, but how about for strings with character values in them? I'm kinda lost, and I don't think I'm going anywhere with this solution.

*UPDATED FURTHER DESCRIPTION :

This will just be a simple grouping algorithm, only the last number will indicate grouping,

AB-1-DF AB-2-DF and AB-3-DF will NOT be grouped to AB-1-DF - AB-3-DF. That simplifies the problem, also the 0 prefix doesn't matter, 001 and 002 can be grouped as 1-2.

The simple rule is basically this :

(character) - (number)
  ABC       -     1 

A difference in character means an entirely different thing.

Answer 1

Here's something that ought to work if sequential items are next to one another. And you'd probably want to write your own are_sequential function:

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

Output:

array(3) {
  [0]=>
  string(3) "1-2"
  [1]=>
  string(1) "4"
  [2]=>
  string(3) "6-8"
}