整数配列の連続区間をハイフンで連結してグループ化する定番のアレ

問題

問題概要

要素に整数を取る配列に関して、以下のように処理する関数を作成せよ。

1. 連続する数字の集合を1つの区間とし、区間最小値と区間最大値をハイフンで連結して1つの文字列とする。区間最小値と区間最大値が等しい場合、その数字をそのまま文字列として扱うこととする。
2. 上記で生成した文字列をまとめて配列として返す。

入力例と出力例

入力

[1,2,3,4,5,8,9,10,13,14,20,22]

出力

["1-5","8-10","13-14","20","22"]

出力用にjson_encodeを使っても良し、単にimplodeで結合しても良し、var_dumpやprint_rでも良し。この処理は関数内に実装する必要はなく、詳細なフォーマットにはここでは拘らないことにする。

制約

• 配列のキーは0番開始の連続した整数
• 配列の値はソート済み
• 配列に重複する値は含まれない

回答例

コード

制約を前提とする場合

function array_group_by_range(array $array, $separator = '-')
{
    $pairs = $ranges = [];
    foreach ($array as $i => $v) {
        $pairs[$v - $i][isset($pairs[$v - $i])] = $v;
    }
    foreach ($pairs as $pair) {
        $ranges[] = implode($separator, $pair);
    }
    return $ranges;
}

echo json_encode(array_group_by_range([1,2,3,4,5,8,9,10,13,14,20,22]));

/* ["1-5","8-10","13-14","20","22"] */

制約を前提としない場合

function array_group_by_range(array $array, $separator = '-')
{
    sort($array, SORT_NUMERIC);
    $pairs = $ranges = [];
    foreach (array_values(array_unique($array, SORT_NUMERIC)) as $i => $v) {
        $pairs[$v - $i][isset($pairs[$v - $i])] = $v;
    }
    foreach ($pairs as $pair) {
        $ranges[] = implode($separator, $pair);
    }
    return $ranges;
}

echo json_encode(array_group_by_range([5,4,8,3,2,9,'a'=>10,14,'b'=>1,20,13,22]));

/* ["1-5","8-10","13-14","20","22"] */

ポイント

• 不連続な値が1つ現れるたびに $v - $i がその差だけ増加するため、$v - $i の値でグループ化すれば連続区間でグループ化したことになる。
• isset($pairs[$v - $i])を第2階層のキーに指定すると、属する第1階層への最初の代入のときに0、それ以降には1という値を取るようになる。これにより、0番目が区間最小値、1番目が区間最大値になる。この方法を採用すると、値が1つしか存在しない場合にも自動的には0番目の要素しか作成されず、区間が存在する場合のみ連結したいと考える場合にはよりシンプルなコードを実現できる。

$v	1	2	3	4	5	8	9	13	14	20	22
$i	0	1	2	3	4	5	6	7	8	9	10
$v - $i	1					3		6		11	12
$pairs[$v - $i][0]	1					8		13		20	22
$pairs[$v - $i][1]	5					9		14		未定義	未定義

応用例

文字の範囲を求める

要素が必ず整数である必要はありません。文字(1バイトの文字列)にも応用することが出来ます。場合によっては正規表現の最適化などで使えるかもしれません。

実装例

function string_group_by_character_range($characters, $separator = '-')
{
    $array = str_split($characters);
    sort($array, SORT_STRING);
    $pairs = $ranges = [];
    foreach (array_values(array_unique($array)) as $i => $v) {
        $ord = ord($v);
        $pairs[$ord - $i][isset($pairs[$ord - $i])] = $v;
    }
    foreach ($pairs as $pair) {
        $ranges[] = implode($separator, $pair);
    }
    return implode('', $ranges);
}

echo string_group_by_character_range("ABCabc01234def56789DEF");

/* 0-9A-Fa-f */