How to find tuples in a list an merge them?

Unity Engine
,
1

I have a list of Game Objects ID, for example, {ID1, ID2, ID3, ID3, ID3, ID2, ID2, ID1, ID2, ID2, ID4}

I need to keep looping through the list and merge Game Objects with similar ID, like this:

First itiration: {ID(1+1), ID2, ID(2+2), ID(2+2), ID3, ID(3+3), ID4} => {ID2, ID2, ID4, ID4, ID3, ID6, ID4}
Second itiration: {ID(2+2), ID(4+4), ID3, ID6, ID4} => {ID4, ID8, ID3, ID6, ID4}
Third itiration: {ID(4+4), ID8, , ID6, ID3} => {ID8, ID8, ID6, ID3}
Fourth itiration: {ID(8+8), ID6, ID3} => {ID16, ID6, ID3}

I have been stuck in this for several hours without any clue! any help is really appreciated!

2

Does it have to be in iterations? If not, just throw them all in a set, which makes then unique, then iterate the set and for each thing in the set, iterate your original collection and remove it.

1 Like
3

Thanks for the answer, but I’m afraid that doesn’t solve my problem, as it will merge the first itiration

4

Well the first part of my solution still works to get you a list of only what is unique.

From your iteration list I’m not able to easily discern a pattern, but perhaps once you know the unique objects you can decide how to proceed?

Or else perhaps just describe your intentions more generically?

5

This sounds like a counting sort! We can just modify the algorithm a bit to combine the copies together.

  • Count how many copies of each number we have. Maybe use a dictionary?
  • Create a new list with one copy of each number (multiplied by the count)

Probably not as-fast-as-possible, but oh well.

Now, if you need to do something more complex – e.g. if each element in the list is more than just a number, and has to have some logic run on it – then that’ll take a bit more work.

6

Uhm, I’m not sure how that applies to “IDs” as an ID is usually an identification number. Since you seem to apply arithmetic on them (so you add two of the same numbers together). Or why does grouping two objects with the ID 3 gives an object with ID6?

To me it looks like you want to combine entries in pairs if they have the same value. The simplest and straight forward solution is to use a source list and a target list where you put the “combined” objects and just use a nested for loop to carry out a single iteration

You made the question deliberately abstract as we don’t know what type your List actually contains and where that ID comes from or where it is stored. If it’s a list of gameobjects, you would probably have a component on them that holds the ID? If that’s the case it would make more sense to use a List of those components. So lets assume each of those gameobjects have a script on them called “ID” and it has a field called “val” that actually represents the value we care about. So it looks like this:

public bool Combine(List<ID> aSource, List<ID> aTarget)
{
    aTarget.Clear();
    bool hasCombinations = false;
    while (aSource.Count > 0)
    {
        ID obj = aSource[0];
        for(int n = 1; n < aSource.Count; n++)
        {
            if (obj.val == aSource[n].val)
            {
                // found a pair, "combine" them and store the combine object in obj
                obj = CombineTwoObjs(obj, aSource[n]);
                // remember that we actually combined something during this method call
                hasCombinations = true;
                // remove the second object from the source list
                aSource.RemoveAt(n)
                // we're done, exit inner loop and continue with outer loop
                break;
            }
        }
        // add current obj to the target list. This is either the object from the source list
        // or our new "combined" object.
        aTarget.Add(obj);
        // remove the first object from source as we are done with it.
        aSource.RemoveAt(0);
    }
    return hasCombinations;
}

You can call this method repeatedly with alternating lists until the method would return false in which case there were no new combinations as we went through the list

So something like that:

public List<ID> Iterate(List<ID> aObjs)
{
    List<ID> tmp = new List<ID>(aObjs);
    List<ID> tmp2 = new List<ID>();
    while (true)
    {
        if (!Combine(tmp, tmp2))
            return tmp2;
        if (!Combine(tmp2, tmp))
            return tmp;
    }
}

This should return a new list with the “combined” objects and it terminates once it can no longer combine them. How you combine them is up to you. The method “CombineTwoObjs” needs to be provided by you. it takes two ID instances as arguments and needs to return the combined object.

7

I’d like to add that your example iterations doesn’t seem to make much sense, especially the “order” which each iteration produces. You as a human are tempted to “combine” the same IDs that are next to each other. However a computer generally just iterates over the list to find the first matching pair. So given your initial list

{ID1, ID2, ID3, ID3, ID3, ID2, ID2, ID1, ID2, ID2, ID4}

After each Combine call you would get those intermediate lists

{ID1, ID2, ID3, ID3, ID3, ID2, ID2, ID1, ID2, ID2, ID4}
{ID2, ID4, ID6, ID3, ID4, ID2, ID4}
{ID4, ID8, ID6, ID3, ID4}
{ID8, ID8, ID6, ID3}
{ID16, ID6, ID3}

So after the first step, the first ID2 is the two ID1s combined, the ID4 is the first ID2 and the second ID2 combined, and so on. So the first iteration would combine the indices (0,7), (1,5), (2,3), 4, (6,8), 9, 10
In the second iteration you get the pairs (0,5), (1,4), 2, 3, 6
After that (0,4), 1, 2, 3
and finally (0,1), 2, 3