Internal comparison and editing of a nested list python
I'm trying to figure something out, the easiest way to explain is using an example:
a = [[1, 2, 4], [2, 5], [0, 3, 7, 8], [12, 3, 6], [18, 14]]
This is the list I start with. I need to compose a list that contains lists of all the lists in the list that have overlapping items added together.
result = [[1, 2, 4, 5], [0, 3, 6, 7, 8, 12], [14, 18]]
How can i do this?
Regards, Daquicker
source to share
a = [[1, 2, 4], [2, 5], [0, 3, 7, 8], [12, 3, 6], [18, 14]]
result = []
for s in a:
s = set(s)
for t in result:
if t & s:
t.update(s)
break
else:
result.append(s)
This will go one by one through the list and create a set from the current sublist ( s
). It then checks the results if there is another set t
that has a non-empty intersection with it. If so, items from s
are added to this set t
. If not t
with non-empty intersection, then it s
is a new independent result and can be added to the list of results.
A similar problem is also a good example for fixed point iteration . In this case, you would look at the list and keep concatenating the sublists while you can still find the lists that overlap. You can implement this with a itertools.combinations
look at subscription pairs:
result = [set(x) for x in a] # start with the original list of sets
fixedPoint = False # whether we found a fixed point
while not fixedPoint:
fixedPoint = True
for x, y in combinations(result, 2): # search all pairs …
if x & y: # … for a non-empty intersection
x.update(y)
result.remove(y)
# since we have changed the result, we haven’t found the fixed point
fixedPoint = False
# abort this iteration
break
source to share
One way I can think of this is recursion. Start with one item, then scroll until you find each number it's connected to. For each of these numbers, you must do the same. Hence recursion. To make it more efficient, store the numbers you visited in a list and check them at the start of each recursive sequence to make sure you don't repeat any research.
source to share
I left the last step for you:
a = [[1, 2, 4], [2, 5], [0, 3, 7, 8], [12, 3, 6], [18, 14]]
result = [[1, 2, 4, 5], [0, 3, 6, 7, 8, 12], [14, 18]]
# each sub list
result2 = []
count = 0
print a
for sub_list in a:
print count
print "sub_list: " + str(sub_list)
a.pop(count)
print "a: " + str(a)
#each int
sub_list_extend_flag = False
for int_in_sub_list in sub_list:
print "int_in_sub_list: " + str(int_in_sub_list)
for other_sub_list in a:
print "current_other_sub_list: " + str(other_sub_list)
if int_in_sub_list in other_sub_list:
sub_list_extend_flag = True
other_sub_list.extend(sub_list)
result2.append(list(set(other_sub_list)))
if not sub_list_extend_flag:
result2.append(sub_list)
count += 1
print result2
source to share
Simple answer:
a = [[1, 2, 4], [2, 5], [0, 3, 7, 8], [12, 3, 6], [18, 14]]
for x in a:
for y in x:
print y
simpler than the first one:
box=[]
a = [[1, 2, 4], [2, 5], [0, 3, 7, 8], [12, 3, 6], [18, 14]]
for x in a:
for y in x:
box.append(y)
print box
Result: [1, 2, 4, 2, 5, 0, 3, 7, 8, 12, 3, 6, 18, 14]
And with that, you can compare numbers:
box=[]
box2=""
a = [[1, 2, 4], [2, 5], [0, 3, 7, 8], [12, 3, 6], [18, 14]]
for x in a:
for y in x:
box.append(y)
print box
for a in box:
box2+=str(a)
print box2
Result: 12425037812361814
Also you can make it prettier:
print " ".join(box2)
Result: 1 2 4 2 5 0 3 7 8 1 2 3 6 1 8 1 4
source to share