Тэги:

Недавно, мне пришло письмо с просьбой решить задачу.

Даны строки:

    Солнце светит ярко
    Ярко светит солнце
    Светит солнце
    Солнце светит
    12345

Как видно, некоторые из строк получены путем переставления слов в других. Задача — убрать неявных злобных клонов.

Сначала я думал перебирать строки брутфорсом. То есть, сравнивать слова и прочее. Но потом Сергей Лунгу подсоветовал их сортировать. Он предложил закодировать каждое слово в строке простой хэш-функцией. Результирующий массив слов-чисел, по его задумке, нужно было отсортировать. В результате, некоторые массивы получились бы идентичными. Их и надо было удалять.

Но подумав, я решил, что идея верна, а реализация слишком мудрена. И решил не применять никаких хэш-функций, а сортировать просто слова.

Думаю, пора уже показать код, который убивает клонов.

function kill_clones($array)  {
    foreach($array as $str) {
        #переводим строку в нижний регистр
        #чтобы исключить влияние регистра
        #ВАЖНО: выставить локаль в скрипте!
        $lcstr = strtolower($str);
        #разбиваем строку на слова
        $wds = split(" ", $lcstr);
        #сортируем слова
        sort($wds, SORT_STRING);
        #собираем строку обратно
        $newstr = join(' ', $wds);
        if(!isset($result[$newstr]))    {
            $result[$newstr] = $str;
        }
    }
    return $result;   
}

Для того, чтобы запомнить какие строки у нас уже были, я использовал ассоциативный массив, ключом которого сделал обработанную строку.

Результат работы скрипта можно увидеть, если запустить что-нибудь в этом духе:

setlocale(LC_ALL, "ru_RU.CP_1251");
$array = Array(
    "Солнце светит ярко",
    "Ярко светит солнце",
    "Светит солнце",
    "Солнце светит",
    "12345"
);
foreach($array as $k=>$v)  {
    print "$v<br/>";
}

$result = kill_clones($array);

print "<pre>";print_r($result);print "</pre>";

foreach($result as $k=>$v)  {
    print "$v<br/>";
}

Надеюсь, я помог человеку, который задал мне этот вопрос по почте. А еще хорошо бы было, если бы этот нехитрый прием пригодился кому-то еще из моих читателей.