CODEWITHSUNDEEP
python
RodericDay
RodericDay

Reputation: 1292

List of lists: Changing all references with one assignment?

Rationale: I start a script with a list that contains multiple heaps. At every step, I want to "join" heaps, but keep both joined indexes pointing to the same element.

In short, given a list of mutable elements, such that list[a] is list[b] returns True, how can I assign (list[a] = [new]) while keeping list[a] and list[b] references to the same mutable container?

So for example, if each heap was represented by a letter, we would have

t is ['a', 'b', 'c', 'd']
t is ['ac', 'b', 'ac', 'd'] (0 and 2 merge)
t is ['abc', 'abc', 'abc', 'd'] (0 and 1 merge, but since 0 also refers to 2, it is as if 0/2 and 1 merged... into 0/1/2)

at this stage, if I did a set(map(id, t)), I would expect it to only have TWO elements.

my problem is that I cannot seem to affect the object being pointed to directly, so I have to iterate over the entire list, picking out any ids that match either merge index, and assign directly.

is there any way to change the underlying object rather than all pointers to it?

Full Example of desired behavior:

>>> my_list = [['a'], ['b'], ['c']]
>>> merge(my_list, 0, 2) # mutates, returns None
>>> my_list
[['a', 'c'], ['b'], ['a', 'c']]
>>> my_list[0] is my_list[2]
True
>>> merge(my_list, 0, 1)
>>> my_list
[['a', 'c', 'b'], ['a', 'c', 'b'], ['a', 'c', 'b']]
>>> my_list[0] is my_list[1]
True
>>> my_list[1] is my_list[2]
True

The problem is that, if within merge I simply call 

my_list[arg1] = my_list[arg2] = my_list[arg1]+my_list[arg2]

it ONLY affects the entries at arg1 and arg2. I want it to affect any other entries that may point to the elements at either my_list[arg1] or my_list[arg2], so that eventually my_list is just a collection of pointers to the same big heap, that has absorbed all the little ones.

Upvotes: 4

Views: 87

Answers (3)

zehnpaard
zehnpaard

Reputation: 6223

As far as I can see, I don't think it's possible to do this using the mutability of python lists. If you have elements X and Y, both of which are already amalgamations of other elements, and you want to merge them, list mutability will not be able to telegraph the change to both sides. You can make X, Y and all the elements pointing at the same object as X be the same, or you can make X, Y and all the elements pointing at the same object as Y be the same, but not both.

I think the best bet is to define a custom object to represent the elements, which has a notion of parent nodes and ultimate parent nodes.

class Nodes(object):
    def __init__(self, input1):
        self.parent = None
        self.val = [input1]

    def ultimate_parent(self):
        if self.parent:
            return self.parent.ultimate_parent()
        else:
            return self

    def merge(self, child):
        self.ultimate_parent().val += child.ultimate_parent().val
        child.ultimate_parent().parent = self.ultimate_parent()

    def __repr__(self):
        return str(self.ultimate_parent().val)

def merge(node_list, i, j):
    node_list[i].merge(node_list[j])


list1 = [Nodes(x) for x in 'abcd']
print list1

merge(list1, 0, 2)
print list1
merge(list1, 1, 3)
print list1
merge(list1, 0, 1)
print list1

This will output:

[['a', 'c'],['b'],['a', 'c'],['d']]
[['a', 'c'],['b', 'd'],['a', 'c'],['b', 'd']]
[['a', 'c', 'b', 'd'],['a', 'c', 'b', 'd'],['a', 'c', 'b', 'd'],['a', 'c', 'b', 'd']]

Upvotes: 1

LittleQ
LittleQ

Reputation: 1925

Chain assignment:

>>> my_list = [['a'], ['b'], ['c']]

>>> my_list[0] = my_list[2] = my_list[0]+my_list[2]

>>> my_list
[['a', 'c'], ['b'], ['a', 'c']]

>>> my_list[0] += [1,2,3]

>>> my_list
[['a', 'c', 1, 2, 3], ['b'], ['a', 'c', 1, 2, 3]]

>>>

If you do a=c=a+c first, it produce a==c==_list_object_001; when you do a=b=a+b 2nd, it produce a==b==_list_object_002, so it went wrong.
You can't do this even with a pointer if you don't take care of the order of assignment. I think you should maintain a map to get things right.

Upvotes: 1

Ethan Furman
Ethan Furman

Reputation: 69051

This is as close as you are going to get:

def merge(primary, first, second):
    primary[first] += primary[second]
    primary[second] = primary[first]

first = ['a']
second = ['b']
third = ['c']

main = [first, second, third]
print(main)
merge(main, 0, 2)
print(main)
assert main[0] is main[2]
merge(main, 0, 1)
print(main)
assert main[1] is main[2]
print(first, second, third)

and the printout:

[['a'], ['b'], ['c']]
[['a', 'c'], ['b'], ['a', 'c']]
[['a', 'c', 'b'], ['a', 'c', 'b'], ['a', 'c', 'b']]
(['a', 'c', 'b'], ['b'], ['c'])

As you can see, the list elements all end up being the same object, but the lists that went into the main list are not.

edit

Unfortunately, this also fails if you don't include the first list element in every merge.

So there are no short-cuts here. If you want every element to either be the same element, or just be equal, you are going to have to traverse the list to get it done:

def merge(primary, first, second):
    targets = primary[first], primary[second]
    result = primary[first] + primary[second]
    for index, item in enumerate(primary):
        if item in targets:
            primary[index] = result

Upvotes: 1

Related Questions