代码之家 › 专栏 › 技术社区 › levi

在AS3中将成对列表转换为数组组

flash actionscript-3 arrays

levi · 技术社区 · 15 年前

我有一个ActionScript3数组,它列出了如下项对:

pairs[0] = Array('ItemA', 'ItemB');
pairs[1] = Array('ItemA', 'ItemC');
pairs[2] = Array('ItemC', 'ItemD');
pairs[3] = Array('ItemC', 'ItemE');
pairs[4] = Array('ItemF', 'ItemG');
pairs[5] = Array('ItemF', 'ItemH');

我需要以某种方式循环数组以找到所有重叠对(共享公共对的任何对)。

例如, ItemA 与 ItemB 和 ItemC ,所以他们属于一个群体。 项目C 也与 ItemD 和 ItemE 所以他们也需要成为第一组的一员。

ItemF , ItemG 和 ItemH 不要与第一组中的任何项目重叠,因此需要将它们放入自己的组中。

生成的数组需要如下所示:

groups[0] = Array('ItemA', 'ItemB', 'ItemC', 'ItemD', 'ItemE');
groups[1] = Array('ItemF', 'ItemG', 'ItemH');

谢谢你的帮助和建议!

编辑:

一点小故事;我正在尝试将在2D中相互重叠的电影片段组合在一起,以创建组或簇(可能是一个更好的词)。

所以如果我在舞台上有3个电影剪辑,ClipA和ClipB重叠,ClipB和ClipC重叠(但ClipA不直接重叠ClipC),它们都应该被组合在一起,因为它们都是同一个集群的一部分。这样,如果新剪辑与群集中的任何单个项重叠,它将被添加到该组的数组中。

我已经编写了代码来查找产生这个pairs列表的重叠元素,现在我需要将其压缩成整齐的组。

3 回复 | 直到 7 年前

Lee 15 年前

像下面的例子这样的算法应该可以工作。

注:这是不编写这段代码的最有效或最简洁的方法(它肯定比需要的重复性更高),但是我想在这个例子中保持它的清晰和简单。[而且,我还没有测试过这段代码--它只是以伪代码的形式出现--所以如果您发现错误,请告诉我,我会修复它]

var idx:Object = new Object;
var groups:Array = new Array();
for( var i:int = 0; i<pairs.length; ++i ) {
   var onePair:Array = pairs[i];

   // which groups do the two items belong to?
   var g1:Array = idx[onePair[0]];
   var g2:Array = idx[onePair[1]];

   if( !g1 ) {
     // if item #1 is not yet in a group, then add it to item #2's
     // existing group, or if neither group exists yet, just create a new one
     g1 = g2;
     if( !g1 ) {
        g1 = [];
        groups.push(g1);
     }
     g1.push( onePair[0] );

     // ensure that the idx properly reflects the location of the new item
     idx[onePair[0]] = g1;
   }

   // now do the same for the second item... but g1 will never be null, so
   // this case is a little simpler.
   if( !g2 ) {
     g2 = g1;
     g2.push( onePair[1] );
     idx[onePair[1]] = g2;
   }

   if( g1 != g2 ) {
      // now, if they're not already the same group, then merge the two
      // groups, and update the idx to reflect the merge.

      for( var z:int=0; z<g2.length; ++z ) {
         idx[g2[z]] = g1;
         g1.push( g2[z] );
         g2.splice(0);
      }
   }
}

groups 最终将成为一个数组数组,正如您所要求的那样——但是会有一些空数组可以被丢弃。删掉(或忽略)空的,你就有了你的小组。

这里的基本思想是 idx 提供一个查找表,在整个索引过程中,对于任何给定的项,指示它所在的组(如果有的话)。这允许我们确定一个项目以前是否遇到过,如果是,则使用它现有的组。

Patrick 15 年前

你可以用 Object 要跟踪一对iten和一个组的关联,密钥将是您的一对中的每一项。

这里是一个小片段,使作品:

var pairs:Array=[];
pairs[0] = ['ItemA', 'ItemB'];
pairs[1] = ['ItemA', 'ItemC'];
pairs[2] = ['ItemC', 'ItemD'];
pairs[3] = ['ItemC', 'ItemE'];
pairs[4] = ['ItemF', 'ItemG'];
pairs[5] = ['ItemF', 'ItemH'];


// will contain group created
var groups:Array=[];

// will contain association between a pair item and a group
var pair2group:Object={};

// function that turn pairs into groups
function makeGroups(pairs:Array):void{
    var pairLen:int = pairs.length;

    for (var i:int=0;i<pairLen;i++){
        var pair:Array = pairs[i];
        var item1:String = pair[0];
        var item2:String = pair[1];

        var group:Array = pair2group[item1];

        // is first pair item already in a group
        if (group == null) {
            // no so create a new group
            group=[];

            // create the association
            pair2group[item1] = group;

            // add the item to the group we have created
            group.push(item1);

            // add it to all the groups 
            groups.push(group);
        }

        // is the second pair item into a grouo
        if (pair2group[item2] == null) {
            // no so add it to the group where the first item belong
            group.push(item2);

            // create the association for the second item
            pair2group[item2] = group;
        }
    }
}

// ---- test
makeGroups(pairs);
trace(groups.length);
trace(groups[0]);
trace(groups[1]);

levi 15 年前

在这里玩了很多次之后,我想出了一个解决办法。

这需要一个2D overlapArray 具有对并生成具有唯一值的组列表的。

我用了一个 in_array() 函数复制PHP的便利函数,用于查找项是否已在数组中。

for each(var pair:Array in overlapArray) {
    var pairInGroup = false;
    for each(var group:Array in overlapArrayGroups) {
        if(in_array(pair[0],group) || in_array(pair[1],group)) {
            if(!in_array(pair[0],group)) {
                group.push(pair[0]);
            }
            if(!in_array(pair[1],group)) {
                group.push(pair[1]);
            }
            pairInGroup = true;
        }
    }
    if(!pairInGroup) {
        overlapArrayGroups.push(pair);
    }
}

这个 在数组中() 功能:

public static function in_array( needle:String, haystack:Array ):Boolean {
    for( var a = 0; a < haystack.length; a++ ) {
        if( haystack[a] == needle ) {
            return true;
        } else if( haystack[a] is Array ) {
            return in_array(needle, haystack[a]);
        }
    }
    return false;
}