Найдите все пересечения между 3 массивами PHP

Question

Найдите все пересечения между 3 массивами PHP

Я в недоумении, как найти все "пары" и "тройки" в 3 массивах PHP. Мои массивы выглядят так:

Array
(
    [0] => Array
        (
            [sanitized] => lisa
            [original] => Lisa
            [weight] => 100
            [color] => blank
        )

    [1] => Array
        (
            [sanitized] => jack
            [original] => Jack
            [weight] => 93
            [color] => blank
        )
    ...

Существует 3 таких массива; они всегда сортируются по целочисленному ключу и всегда содержат 10 индексов (0-9). То, что я пытаюсь сделать, это:

Найдите экземпляры одинаковых имен (путем сравнения "очищенного" поля) либо в 2 массивах, либо во всех 3 массивах и измените их "цвет" на одинаковый (т.Е. Я не хочу находить только пересечение между всеми 3 массивами - это можно сделать с помощью array_intersect)
Создайте 4-й массив, который объединяет все записи и объединяет одинаковые имена (путем сравнения "очищенного" поля) путем суммирования их весов (цвета не имеют значения)
Поскольку эти задачи похожи, я хотел бы выполнять их одновременно и минимизировать сложность

Это трудно объяснить, поэтому я представил это визуально.

Цвета:

Цвета http://www.tsiomenko.com/1.png

Веса:

Веса http://www.tsiomenko.com/2.png

У меня есть немного рабочего кода, но он действительно длинный, уродливый и имеет сложность примерно N^3 - я использую вложенные циклы for для многократного обхода всех массивов, пока не получу то, что мне нужно. Несмотря на то, что я работаю с действительно небольшими массивами, я хотел бы знать, как это сделать эффективно, потому что мне любопытно, как другие будут подходить к этой проблеме. Псевдокод о том, как подход к этой проблеме, а не PHP, приветствуется.

2

php data-structures set asymptotic-complexity

Author: user1890572, 2013-01-08

Source

1 answers

score 1 · Accepted Answer

Следующий цикл должен выдавать необходимый вам результат:

// loop once to build the combined array and set the colors
foreach ($names as &$name) {
    if (!isset($combined[$name['sanitized']])) {
        $combined[$name['sanitized']] = array(
            'original' => $name['original'],
            'weight'   => $name['weight'],
            'color'    => array_pop($colors),
            'count'    => 1,
        );
    } elseif ($combined[$name['sanitized']]['count'] < 3) {
        $combined[$name['sanitized']]['weight'] += $name['weight'];
        $combined[$name['sanitized']]['count']++;
    }

    $name['color'] = $combined[$name['sanitized']]['color'];
}


// loop again to blank any colors where name only appeared once
foreach ($names as &$name) {
    if ($combined[$name['sanitized']]['count'] === 1) {
        $combined[$name['sanitized']]['color'] = $name['color'] = 'blank';
    }
}

Я опустил генератор цветов, для которого существует много вопросов SO. Одна вещь, которая здесь остается несколько неясной, - это то, что делать, если найдено более 3 совпадений, поэтому вам, вероятно, придется изменить вышеизложенное в соответствии с вашими потребностями.

Вот суть и вот сгенерированный результат.