En busca del algoritmo con datos similares de grupo

Question

Una simple pregunta, pero la respuesta que me ha estado atormentando durante días ...

tengo como entrada una matriz (php) de 2 alias, digamos:

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

Cada uno de los estado "1" es lo mismo que "5", "6" es lo mismo que "8", ... simple, ahora necesitan agrupar los, mirando el ejemplo anterior , el algoritmo debería darme, si lo pido amablemente, dos grupos:

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

lógica de conmutación simple, pero no puedo encontrar una manera de abordarlo con el código! ¡Cualquier directriz sería muy apreciada!

Answer 1

Construiría algún tipo de árbol a partir de estos y usaría la coloración para separar los componentes. Por ejemplo, dejar G = [E, V], E = {1, 5, 6, 7, 9}, V = {{1,5}, {6,8}, {6,1}, {9, 3}} donde G es un gráfico con V vértices y bordes E. Ahora comience con un vértice aleatorio, que coloreará recursivamente todo su vecino para colorear C1 (con búsqueda de amplitud primero). Si no puedes encontrar nuevos vecinos, obtienes el primer grupo. Ahora comience con un nuevo vértice sin color y un nuevo color C2. Repite esto hasta que no tengas más vértices.

Answer 2

Esta es una instancia de un problema de unión conjunto disjunto.

Wikipedia tiene una página sobre ello aquí:

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

Hay algunos algoritmos de muestra que resuelven el problema en la página de Wikipedia. ¿Es wikipedia suficientemente clara para ti?

Answer 3

Puede hacer esto increíblemente rápido utilizando el algoritmo union-find.

La idea es tener un bosque de árboles, donde cada árbol representa elementos "que son iguales". Usted representa este árbol como una matriz simple, donde un [i] puede ser el padre de i, -1 si yo soy la raíz, o decir -2 si todavía no estoy en un árbol.

En su caso sería empezar con la simple árbol:

1 
\ 
    5 

La siguiente cosa que usted quiere que se unen a 6 y 8. Sin embargo, ambos están sin asignar, por lo que se agrega un nuevo árbol. (Esa es una [6] = - 1, una [8] = 6):

1 6 
\ \ 
    5 8 

ahora quiere unirse a 6 y 1. Usted descubre que establece que pertenecen, siguiendo a sus padres a la parte superior. Casualmente, ambos son raíces. En este caso, hacemos que el árbol más pequeño sea el hijo del otro árbol. (Una [6] = 1)

1 
/\ 
6 5 
\ 
    8 

Finalmente queremos unirnos a 9 y 3, ambos están sin asignar, por lo que crear un nuevo árbol. (a [3] = - 1, a [9] = 3)

1 9 
/\ \ 
6 5 3 
\ 
    8 

Supongamos que también tiene 5 = 3? Sigue a sus padres hasta que llegues a las raíces. Descubres que ya no son iguales, por lo que fusionas los árboles.Desde el 9 controla un árbol menos alto, lo añadimos a uno de árbol, para obtener:

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

Como se puede ver ahora es fácil para comprobar si dos elementos están en el mismo conjunto. Digamos que quieres probar si 8 y 3 son iguales? Solo sigan sus caminos hacia arriba, y verán que 8 está en el conjunto representado por uno, y tres en el conjunto representado por 9. Por lo tanto, son desiguales.

Usando la heurística de poner siempre el árbol más pequeño debajo del más grande, te da un log (n) promedio de búsqueda o tiempo de fusión. El artículo de Wikipedia explica un truco adicional, que básicamente lo convertirá en tiempo constante.

Answer 4

<?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());