Convert Liste von Paaren in Array-Gruppen in AS3

Question

Ich habe eine Actionscript-3-Array, die Paare von Elementen wie folgt aufgeführt:

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');

Und ich brauche in irgendeiner Weise über die Anordnung in einer Schleife alle überlappende Paare zu finden (alle Paare, die gemeinsame Paare haben).

Zum Beispiel ist ItemA mit ItemB und ItemC gepaart, so dass sie in einer Gruppe zusammen gehören. ItemC ist auch mit ItemD und ItemE gepaart, so dass sie auch ein Teil der ersten Gruppe sein müssen.

ItemF, ItemG und ItemH überschneiden sich nicht mit irgendwelchen Elementen aus der ersten Gruppe, also müssen sie in ihre eigene Gruppe gestellt werden.

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

Vielen Dank für jede Hilfe und Anregungen:

Das resultierende Array wäre so etwas wie sein müssen!

Edit:

Ein wenig von einer Hintergrundgeschichte; Ich versuche, Filmclips zu gruppieren, die sich in 2D überlappen, um Gruppen oder Cluster zu erstellen (möglicherweise ein besseres Wort).

Wenn ich also 3 MovieClips auf der Bühne habe und ClipA überlappt mit ClipB und ClipB überlappt ClipC (aber ClipA überlappt ClipC nicht direkt) sollten sie alle zusammen gruppiert werden, da sie alle Teil desselben Clusters sind. Auf diese Weise sollte ein neuer Clip ein einzelnes Element in einem Cluster überlappen und wird dem Array dieser Gruppe hinzugefügt.

Ich habe bereits den Code ausgearbeitet, um überlappende Elemente zu finden, die diese Paare Liste produziert, jetzt muss ich es in saubere Gruppen zusammenfassen.

Answer 1

Nach viel Herumspielen ist hier die Lösung, die ich mir ausgedacht habe.

Dies erfordert eine 2D overlapArray, die Paare hat und eine Gruppenliste mit eindeutigen Werten erzeugt.

Ich habe eine in_array() Funktion verwendet, um die praktische Funktion von PHP zu duplizieren, um herauszufinden, ob sich ein Element bereits in einem Array befindet.

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

Die in_array() Funktion:

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

Ein Algorithmus wie das folgende Beispiel sollte funktionieren.

HINWEIS: Dies ist nicht der effizienteste oder prägnanteste Weg, um diesen Code zu schreiben (es ist sicherlich wiederholender als es sein muss), aber ich wollte es klar und einfach für dieses Beispiel zu halten. [Auch ich habe diesen Code nicht getestet - es wird als Pseudo-Code nur vorgestellt wird - also, wenn Sie einen Fehler finden, lassen Sie es mich wissen, und ich werde ihn beheben]

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 wird Am Ende ist es ein Array von Arrays, genau wie du es verlangst - aber es wird ein paar leere Arrays geben, die verworfen werden können. Beschneide (oder ignoriere) einfach die leeren und du hast deine Gruppen.

Die Grundidee hier ist, dass idx eine Nachschlagetabelle zur Verfügung stellt, die während des gesamten Indexierungsprozesses für jedes gegebene Element angibt, in welcher Gruppe es sich befindet (falls vorhanden). Auf diese Weise können wir feststellen, ob ein Artikel bereits gefunden wurde oder nicht, und falls dies der Fall ist, um seine vorhandene Gruppe zu verwenden.

Answer 3

Sie können eine Object verwenden, um die Spur der Vereinigung eines Paares Iten und einer Gruppe zu halten, wird der Schlüssel jedes Element Ihres Paar sein.

hier ein litle Snippet, das die Arbeiten machen:

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]);