logo标签列表

寻找用于分组相似数据的算法

phpalgorithm
6

一个简单的问题，但是答案却让我苦恼了好几天...

我有一个包含 2 个别名的数组（PHP）作为输入，比如：

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)

简单的通讯逻辑，但我找不到用代码解决的方法！非常感谢任何指导！！
找到你的问题的算法非常有趣，谢谢 :) - OZ_
请查看我的答案，那里有完整的解决方案。 - OZ_
4个回答
2
你可以使用并查集算法来快速完成这个操作。
其思想是将元素“相等”的森林表示为一组树。你可以将每个树表示为一个简单的数组，其中 a[i] 要么是 i 的父节点，如果 i 是根节点则为 -1，如果 i 还没有加入树中则为 -2。
在你的情况下，你可以从简单的树开始：
1   
 \  
  5

下一步，您需要将6和8加入。但是，它们都没有被分配，因此您需要添加一个新的树。（也就是a[6]=-1, a[8]=6）：
1    6   
 \    \  
  5    8

现在你想要将6和1相加。你需要跟随它们的父节点一直到顶部，找出它们所属的集合。巧合的是，它们都是根节点。在这种情况下，我们将较小的树作为另一棵树的子节点。（a[6]=1）

  1  
 / \ 
6   5
 \
  8

最后，我们想要将数字9和3相连，它们都没有被分配，因此我们创建了一棵新的树。(a[3]=-1, a[9]=3)
  1    9
 / \    \
6   5    3
 \
  8

假设你也有5=3？跟随它们的父节点直到达到根节点。你会发现它们并不相等，所以你需要合并这些树。由于9控制着一棵较低的树，我们将它添加到1的树中，得到：

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

从上面的内容可以看出，现在检查两个元素是否在同一集合中变得很容易。比如你想测试8和3是否相等？只需沿着它们向上的路径走，你会发现8在由1表示的集合中，而3在由9表示的集合中。因此它们是不相等的。

始终将较小的树放在较大的树下的启发式方法，平均查找或合并时间为log(n)。维基百科文章解释了一个额外的技巧，使其基本上成为常数时间。

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

我会从这些中构建一些树，并使用着色来分隔组件。例如，让G=[E,V]，其中E={1, 5, 6, 7, 9}，V={{1,5},{6,8},{6,1},{9,3}}是一个具有V个顶点和E条边的图形。现在从一个随机顶点开始，然后递归地将它的所有邻居涂上颜色C1（使用广度优先搜索）。如果找不到新的邻居，则得到第一组。现在从一个未着色的新顶点和一个新颜色C2开始。重复此过程，直到没有更多的顶点。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接