Updating a list of tuples if a value appears in a different set of tuples

user_13752017 0
Viewed 124

Lets say i have a list of tuples

tl = [("x","y"), ("y","z"), ("y","a")]

and for every tuple in the list I want to replace the occurrence of the first item in the tuple in the rest of the tuples except the tuple I'm currently working with so it would be something like this.

First iteration: This is the first tuple in the list: ("x","y")

Now I want to find if "x" appears in any of the other tuples except the tuple I'm currently working with. Since there aren't any other "x"'s the list will stay the same.

After:

tl = [("x","y"), ("y","z"), ("y","a")]

Second iteration: This is the second tuple in the list: ("y","z")

I want to find if "y" appears in any of the other tuples except the tuple I'm currently working with. In this case there is another "y" in the third tuple ("y","a") so we have to replace it with "z".

After: The third tuple was changed from ("y","a") to ("z","a")

tl = [("x","z"), ("y","z"), ("z","a")]

Third iteration: This is the third tuple in the list ("z","a").

I want to find if "z" appears in any of the other tuples except the one I'm currently working with and replace "z" with "a". In this case "z" appears in the first and second tuple.

After: The first tuple changed from ("x","z") to ("x","a"). The second tuple changed from ("y","z") to ("y","a").

tl = [("x","a"), ("y","a"), ("z","a")]

Since we already iterated all the items in the list we can stop and [("x","a"), ("y","a"), ("z","a")] is the result.

What would be the most efficient way to achieve this? and will it be easier to achieve it if I have a dictionary instead?

tuples list python
3 Answers

This is O(n^2), which is the most efficient way until proven otherwise ;)

tl = [("x","y"), ("y","z"), ("y","a")]

for i, (find, replace) in enumerate(tl):
    for j, t in enumerate(tl):
        if j != i:  # Skip self
            tl[j] = tuple(replace if x == find else x for x in t)

print(tl)  # -> [('x', 'a'), ('y', 'a'), ('z', 'a')]

I don't know how you would use a dict for this.

user_45183410

You can create a dictionary at the beginning with references to items in output list:

tl = [("x", "y"), ("y", "z"), ("y", "a")]

out, d = [], {}
for i, (a, b) in enumerate(tl):
    l = [a, b]
    out.append(l)
    d.setdefault(a, []).append((i, l))
    if a != b:
        d.setdefault(b, []).append((i, l))

for i, (a, b) in enumerate(out):
    for idx, l in d.get(a, []):
        if idx != i:
            if l[0] == a:
                l[0] = b
            if l[1] == a:
                l[1] = b
            d[a].remove((idx, l))
            d[b].append((idx, l))

print(out)

Prints:

[['x', 'z'], ['y', 'a'], ['z', 'a']]
user_100359850

Tuples are immutable, therefore I think you're better off using a dictionary.

Here is my solution

tl = [("x","y"), ("y", "z"), ("y","a")]

def my_function(tl):
    ll = [list(tup) for tup in tl]
    llen = len(ll)
    for i in range(llen):
        for j in range(llen):
            if j==i:
                continue
            if ll[i][0] == ll[j][0]:
                ll[j][0] = ll[i][1]

            if ll[i][0] == ll[j][1]:
                ll[j][1] = ll[i][1]

    res = [tuple(l) for l in ll]
    return res

tl = my_function(tl)
print(tl) # -> [('x', 'a'), ('y', 'a'), ('z', 'a')]

"i" will serve as the current list that is referenced and "j" is the list that is being changed if need be. The inner loop skips over the list being referenced.

Let me know if you have any questions or if you find any problems with the code.

user_128543840
Related