Auf der Suche nach einem Algorithmus zur Gruppierung ähnlicher Daten

Question

Eine einfache Frage, aber eine Antwort, die mich seit Tagen quält ...

Ich habe als Eingabe ein Array (PHP) von 2 Aliassen, sagen wir:

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

Jeder von ihnen sagt "1" ist dasselbe wie "5", "6" ist dasselbe wie "8",... Einfach, jetzt muss ich diese gruppieren, wenn ich mir das obige Beispiel anschaue, sollte der Algorithmus mir, wenn ich nett frage, zwei Gruppen geben:

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

Einfache Vertauschungslogik, aber ich kann keinen Weg finden, es mit Code zu lösen! Jeder Leitfaden wäre sehr geschätzt!!

Answer 1

Sie können dies extrem schnell mit dem Union-Find-Algorithmus tun.

Die Idee ist, einen Wald von Bäumen zu haben, wobei jeder Baum Elemente "darstellt, die gleich sind". Sie stellen diesen Baum als einfaches Array dar, wobei a[i] entweder der Elternteil von i sein kann, -1 wenn i die Wurzel ist, oder -2, wenn i noch nicht in einem Baum ist.

In Ihrem Fall würden Sie mit dem einfachen Baum beginnen:

1   
 \  
  5 

Als nächstes möchten Sie 6 und 8 verbinden. Da sie beide nicht zugeordnet sind, fügen Sie einen neuen Baum hinzu. (Das heißt a[6]=-1, a[8]=6):

1    6   
 \    \  
  5    8 

Nun möchten Sie 6 und 1 verbinden. Sie finden heraus, zu welchen Sets sie gehören, indem Sie ihren Eltern bis nach oben folgen. Zufälligerweise sind sie beide Wurzeln. In diesem Fall machen wir den kleineren Baum zum Kind des anderen Baums. (a[6]=1)

  1  
 / \ 
6   5
 \
  8

Zuletzt möchten wir 9 und 3 verbinden, da sie beide nicht zugeordnet sind, erstellen wir einen neuen Baum. (a[3]=-1, a[9]=3)

  1    9
 / \    \
6   5    3
 \
  8

Angenommen, Sie haben auch 5=3? Folgen Sie ihren Eltern, bis Sie die Wurzeln erreichen. Sie stellen fest, dass sie nicht schon gleich sind, also vereinen Sie die Bäume. Da die 9 einen weniger hohen Baum steuert, fügen wir sie dem Baum von 1 hinzu, um zu erhalten:

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

Wie Sie sehen können, ist es jetzt einfach zu überprüfen, ob zwei Elemente im selben Set sind. Möchten Sie beispielsweise testen, ob 8 und 3 gleich sind? Folgen Sie einfach ihren Pfaden nach oben, und Sie werden sehen, dass 8 im Set von eins und drei im Set von 9 liegt. Daher sind sie ungleich.

Mit der Heuristik, den kleineren Baum immer under den größeren zu setzen, erhalten Sie eine durchschnittliche Find- oder Merge-Zeit von log(n). Der Wikipedia-Artikel erklärt einen zusätzlichen Trick, der es im Grunde genommen zu konstanter Zeit macht.

Answer 2

Ich würde aus diesen eine Art Baum aufbauen und Kolorierung verwenden, um Komponenten zu trennen. Zum Beispiel sei G = [E, V], E = {1, 5, 6, 7, 9}, V = { {1,5}, {6,8}, {6,1}, {9,3} }, wobei G ein Graph mit V Vertices und E Kanten ist. Beginnen Sie nun mit einem zufälligen Vertex, dann färben Sie rekursiv alle seine Nachbarn mit der Farbe C1 ein (mit Breitensuche). Wenn Sie keine neuen Nachbarn finden können, haben Sie die erste Gruppe gefunden. Beginnen Sie nun mit einem neuen ungefärbten Vertex und einer neuen Farbe C2. Wiederholen Sie dies, bis Sie keine Vertices mehr haben.

Answer 3

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 4

Dies ist eine Instanz eines Problems mit disjunkten Mengenvereinigungen.

Wikipedia hat eine Seite dazu hier:

http://de.wikipedia.org/wiki/Unions-Find-Problem

Es gibt auf der Wikipedia-Seite einige Beispielsalgorithmen, die das Problem lösen. Ist Wikipedia für dich klar genug?