轉換列表

Question

我有一個ActionScript 3數組，列出項目配對是這樣的：

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配對，因此它們屬於一個羣組。 ItemC也與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重疊），它們應該全部組合在一起，因爲它們都是同一個集羣的一部分。這樣一個新的剪輯應該與羣集中的任何單個項目重疊，它將被添加到該羣組的數組中。

我已經得到了代碼，找出產生這對列表的重疊元素，現在我需要將它壓縮成整齊的組。

Answer 1

大量玩弄這裏的解決方案後，我想出了。

這將需要一個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); 
    } 
} 

的in_array()功能：

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; 
} 

Answer 2

像下面的例子算法應該工作。

注意：這是而不是這是編寫此代碼的最有效或簡潔的方式（它肯定比它需要重複得多），但我希望在本例中保持清晰和簡單。 [此外，我還沒有測試此代碼 - 它表現爲僞代碼只 - 所以，如果您發現錯誤，請讓我知道了，我會解決它]

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提供了一個查找表，它在整個索引過程中指示任何給定的項目，它在哪個組中（如果有的話）。這使我們能夠確定一個項目是否曾經遇到過，如果是，就利用它的現有組。

Answer 3

您可以使用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]);