В поисках алгоритма для группировки похожих данных

Question

Простой вопрос, но ответ, который мучил меня несколько дней ...

В качестве входных данных у меня есть массив (php) из 2 псевдонимов, скажем:

Array(
  Array(1,5),
  Array(6,8),
  Array(6,1),
  Array(9,3),
)

Каждое из этих состояний "1" такое же, как "5", "6" такое же, как "8", ... Просто, теперь мне нужно сгруппировать их, глядя на приведенный выше пример, алгоритм должен дать мнеЕсли я правильно спрашиваю, две группы:

Array(1,5,6,8) and Array(9,3)

Простая логика коммутации, но я не могу найти способ справиться с ней с помощью кода!Любое руководство будет высоко ценится !!

Answer 1

Вы можете сделать это безумно быстро, используя алгоритм поиска объединения.

Идея состоит в том, чтобы иметь лес из деревьев, где каждое дерево представляет элементы "равные". Вы представляете это дерево как простой массив, где a [i] может быть родительским для i, -1, если i является корнем, или сказать -2, если i еще нет в дереве.

В вашем случае вы бы начали с простого дерева:

1   
 \  
  5 

Следующее, что вы хотите, чтобы это присоединилось к 6 и 8. Однако они оба не назначены, поэтому вы добавляете новое дерево. (То есть [6] = - 1, a [8] = 6):

1    6   
 \    \  
  5    8 

Теперь вы хотите присоединиться к 6 и 1. Вы узнаете, к каким наборам они принадлежат, следуя за своими родителями наверх. По совпадению они оба корни. В этом случае мы делаем самое маленькое дерево дочерним по отношению к другому дереву. (А [6] = 1)

  1  
 / \ 
6   5
 \
  8

Наконец, мы хотим объединить 9 и 3, они оба не назначены, поэтому мы создаем новое дерево. (a [3] = - 1, a [9] = 3)

  1    9
 / \    \
6   5    3
 \
  8

Скажите, у вас также есть 5 = ​​3? Следуйте за своими родителями, пока не дойдете до корней. Вы обнаружите, что они уже не равны, поэтому вы сливаете деревья. Поскольку 9 управляет менее высоким деревом, мы добавляем его к своему дереву, чтобы получить:

  .1.
 / | \
6  9  5
 \  \
  8  3

Как видите, теперь легко проверить, находятся ли два элемента в одном наборе. Скажи, хочешь проверить, равны ли 8 и 3? Просто следуйте по их путям вверх, и вы увидите, что 8 в наборе, представленном одним, и три в наборе, представленном 9. Следовательно, они неравны.

Использование эвристики всегда помещая меньшее дерево под большее, дает вам log (n) среднее время поиска или слияния. Статья в Википедии объясняет дополнительный трюк, который сделает его в основном постоянным.

Answer 2

<?php

class AliasesFinder
{
    /** @var array */
    protected $chains;
    /** @var array */
    protected $aliases;
    protected $digits;

    public function __construct($aliases)
    {
        $this->aliases = $aliases;

        //collect all digits
        $digits = array();
        foreach ($this->aliases as $alias_pair)
        {
            if (!in_array($alias_pair[0], $digits)) $digits[] = $alias_pair[0];
            if (!in_array($alias_pair[1], $digits)) $digits[] = $alias_pair[1];
        }
        $this->digits = $digits;
    }

    public function find_all_aliases($digit, &$chain = array())
    {
        //if $digit already in some chain - return, don't spend time to count another time
        if (!empty($this->chains))
        {
            foreach ($this->chains as $existing_chain)
            {
                if (in_array($digit, $existing_chain)) return false;
            }
        }

        //$digit is part of chain already
        $chain[] = $digit;

        foreach ($this->aliases as $alias_pair)
        {
            //if alias of digit not in chain yet - add this alias-digit and all aliases of this alias-digit to chain
            if ($digit==$alias_pair[0] && (empty($chain) || !in_array($alias_pair[1], $chain)))
            {
                $this->find_all_aliases($alias_pair[1], $chain);
            }
            elseif ($digit==$alias_pair[1] && (empty($chain) || !in_array($alias_pair[0], $chain)))
            {
                $this->find_all_aliases($alias_pair[0], $chain);
            }
        }
        return $chain;

    }

    public function getChains()
    {
        foreach ($this->digits as $digit)
        {
            $aliases = $this->find_all_aliases($digit);
            if ($aliases!==false) $this->chains[] = $aliases;
        }
        return $this->chains;
    }
}

$aliases = Array(
    Array(1, 5),
    Array(6, 8),
    Array(6, 1),
    Array(9, 3),
);

$finder = new AliasesFinder($aliases);
print_r($finder->getChains());

Answer 3

Я бы построил какое-то дерево из них и использовал бы раскраску для разделения компонентов. Например, пусть G = [E, V], E = {1, 5, 6, 7, 9}, V = {{1,5}, {6,8}, {6,1}, {9,3 }} где G - граф с V вершинами и E ребрами. Теперь начните со случайной вершины, а затем рекурсивно раскрасьте всю ее соседку по цвету C1 (с поиском в ширину). Если вы не можете найти новых соседей, у вас есть первая группа. Теперь начните с новой неокрашенной вершины и нового цвета C2. Повторяйте это до тех пор, пока у вас не останется больше вершин.

Answer 4

Это пример проблемы объединения несвязных множеств.

В Википедии есть страница об этом здесь:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

На странице википедии есть несколько примеров алгоритмов, которые решают проблему. Достаточно ли понятна для вас Википедия?