在2D数组中创建类似元素的集合

Question

我正在尝试解决基于2D阵列的问题.该数组包含不同类型的元素(总共3种可能的类型).让我们假设为X,Y,Z.

该数组似乎是这样的.请注意,它将始终完全填充.该图用于说明.

7 | | | | | | |
6 | | | | | | |
5 | | | | | | |
4 | |X|Z|Y|X| |
3 | |Y|X|Y|Y|X|
2 |Y|Y|X|Z|Z|X|
1 |X|X|Y| |X|X|
0 | | | |Z| | |
   0 1 2 3 4 5

我正在尝试创建彼此相邻放置的元素集.例如,set1可以包括位于以下的类型X的元素:(0,1),(1,1),(2,2),(2,3),(1,4).类似地,set2可以包括位于以下的类型Y的元素:(3,4),(3,3),4,3).

问题:给定数组中的任何一点,它必须能够将所有元素添加到适当的集合,并确保没有两个集合包含相同的元素.请注意,只有遇到两个以上相同类型的相邻元素时才会创建一个集合.

此外,如果删除了某个元素子集,则会添加更多元素来替换删除的元素.然后必须重新迭代该数组以创建新集或修改现有集.

解决方案:我实现了一个递归解决方案,以便迭代所有相邻元素,例如元素X(0,1).然后,在迭代8个可能的相邻元素时,只要发生类型X,它就会递归调用自身.

这种解决方案过于暴力和低效,特别是在某些元素被可能不同类型的新元素替换的情况下.在这种情况下,几乎整个数组必须重新迭代以制作/修改集合并确保在多个集合中不存在相同的元素.

有没有算法可以有效地处理这类问题？我需要一些想法/建议或伪代码的帮助.

Answer 1

[编辑2013年5月8日:固定时间复杂性.(O(a(n))基本上是恒定的时间!)]

在下文中,"连通分量"是指通过仅允许具有相同种类元素的相邻位置之间的水平,垂直或对角线移动的路径彼此可到达的所有位置的集合.例如,您的示例{(0,1), (1,1), (2,2), (2,3), (1,4)}是示例输入中的连接组件.每个位置都属于一个连接的组件.

我们将构建一个联合/查找数据结构,用于为每个位置(x,y)提供一个数字"标签",该标签具有以下属性:当且仅当任何两个位置(x,y)和(x',y') )属于相同的组件,然后他们有相同的标签.特别是此数据结构支持三种操作:

• set(x, y, i) 将位置(x,y)的标签设置为i.
• find(x, y) 将返回分配给位置(x,y)的标签.
• union(Z)对于某些标签集合Z,将Z中的所有标签组合成单个标签k,在某种意义上,未来find(x, y)对先前在Z中具有标签的任何位置(x,y)的调用现在将返回k.(通常k将是Z中已经存在的标签之一,尽管这实际上并不重要.) union(Z)也会返回新的"主"标签k.

如果总共有n = width*高度位置,则可以在O(n*a(n))时间内完成,其中a()是极慢增长的逆Ackermann函数. 对于所有实际输入大小,这与O(n)相同.

请注意,每当两个顶点彼此相邻时,有四种可能的情况:

1. 一个在另一个之上(由垂直边缘连接)
2. 一个是另一个的左边(通过水平边缘连接)
3. 一个在另一个的上方和左侧(由\对角线边缘连接)
4. 一个在另一个的上方和右侧(由/对角线边缘连接)

我们可以使用以下过程来确定每个位置(x,y)的标签:

• 将nextLabel设置为0.
• 对于每一行y按升序排列:
  • 对于每列x按升序排列:
    • 检查(x,y)的W,NW,N和NE邻居.设Z是这4个邻居的子集,与(x,y)相同.
    • 如果Z是空集,那么我们暂时假设(x,y)启动一个全新的组件,所以调用set(x,y,nextLabel)并递增nextLabel.
    • 否则,在Z的每个元素上调用find(Z [i])来查找它们的标签,并在这组标签上调用union()将它们组合在一起.将新标签(此union()调用的结果)分配给k,然后调用set(x,y,k)将(x,y)添加到此组件.

在此之后,调用find(x, y)任何位置(x,y)可以有效地告诉您它属于哪个组件.如果您希望能够快速回答"哪些位置属于包含位置(x,y)的连通组件？"形式的查询？然后创建一个列表哈希表,posInComp并在输入数组上进行第二次传递,将每个(x,y)附加到列表中posInComp[find(x, y)].这可以在线性时间和空间中完成.现在回答一些给定位置(x,y)的查询,只需调用lab = find(x, y)以找到该位置的标签,然后列出位置posInComp[lab].

要处理"太小"的组件,只需看看它的大小posInComp[lab].如果它是1或2,则(x,y)不属于任何"足够大"的组件.

最后,所有这些工作都需要线性时间,因此除非你的输入数组很大,否则它会很快.因此,在修改输入数组后从头重新计算它是完全合理的.

Answer 2

在你的情况下，我至少会依赖两个不同的数组：

Array1 (sets) -> all the sets and the associated list of points. Main indices: set names.
Array2 (setsDef) -> type of each set ("X", "Y" or "Z"). Main indices: type names.

可能可以创建更多支持数组，例如，包含每组的最小/最大 X/Y 值的数组，以加快分析速度（尽管无论如何都会很快，如下所示）。

您没有提到任何编程语言，但我提供了一个示例（C#）代码，因为它是解释这一点的最佳方式。请不要将其理解为最佳继续方式的建议（就个人而言，我不太喜欢Dictionaries/Lists太多；尽管认为这确实提供了一种很好的图形方式来显示算法，即使对于没有经验的 C# 用户也是如此）。此代码仅旨在展示数据存储/检索方法；实现最佳性能的最佳方法取决于目标语言和其他问题（例如数据集大小），并且是您必须注意的事情。

Dictionary<string, List<Point>> sets = new Dictionary<string, List<Point>>(); //All sets and the associated list of points
Dictionary<string, List<string>> setsDef = new Dictionary<string, List<string>>(); //Array indicating the type of information stored in each set (X or Y)

List<Point> temp0 = new List<Point>();
temp0.Add(new Point(0, 0));
temp0.Add(new Point(0, 1));
sets.Add("Set1", temp0);
List<String> tempX = new List<string>();
tempX.Add("Set1");

temp0 = new List<Point>();
temp0.Add(new Point(0, 2));
temp0.Add(new Point(1, 2));
sets.Add("Set2", temp0);
List<String> tempY = new List<string>();
tempY.Add("Set2");

setsDef.Add("X", tempX);
setsDef.Add("Y", tempY);


//-------- TEST
//I have a new Y value which is 2,2
Point targetPoint = new Point(2, 2);
string targetSet = "Y";

//I go through all the Y sets
List<string> targetSets = setsDef[targetSet];

bool alreadyThere = false;
Point candidatePoint;
string foundSet = "";
foreach (string set in targetSets) //Going through all the set names stored in setsDef for targetSet
{
    List<Point> curPoints = sets[set];
    foreach (Point point in curPoints) //Going through all the points in the given set
    {
        if (point == targetPoint)
        {
            //Already-stored point and thus the analysis will be stopped
            alreadyThere = true;
            break;
        }
        else if (isSurroundingPoint(point, targetPoint))
        {
            //A close point was found and thus the set where the targetPoint has to be stored
            candidatePoint = point;
            foundSet = set;
            break;
        }
    }
    if (alreadyThere || foundSet != "")
    {
        break;
    }
}

if (!alreadyThere)
{
    if (foundSet != "")
    {
        //Point added to an existing set
        List<Point> curPoints = sets[foundSet];
        curPoints.Add(targetPoint);
        sets[foundSet] = curPoints;
    }
    else
    {
        //A new set has to be created
        string newName = "New Set";
        temp0 = new List<Point>();
        temp0.Add(targetPoint);
        sets.Add(newName, temp0);

        targetSets.Add(newName);
        setsDef[targetSet] = targetSets;
    }
}

哪里isSurroundingPoint有一个函数检查两个点是否彼此接近：

private bool isSurroundingPoint(Point point1, Point point2)
{
    bool isSurrounding = false;
    if (point1.X == point2.X || point1.X == point2.X + 1 || point1.X == point2.X - 1)
    {
        if (point1.Y == point2.Y || point1.Y == point2.Y + 1 || point1.Y == point2.Y - 1)
        {
            isSurrounding = true;
        }
    }
    return isSurrounding;
}