# Algorithm Python

Hi, I am not able to achieve a good algorithm to do this, if anyone can help please:

I need to put all similars in the same list.

`[[0, 11], [0, 16], [12, 8], [12, 9]]`

so it would be like this:

`[[0, 11, 16], [8, 9, 12]]`

Thank you!

joao

Youâ€™re going to need to be a lot more precise.
What are â€śsimilarsâ€ť in your context?
What are you actually doing with the numbers? There may be a better way to phrase your problem.

I have a guess what you might mean, so what do you do if you have this list
`[[1, 2], [3, 4], [2, 3]]` ? The first and last items in the list donâ€™t share any values, but the middle one does.

Are you trying to take a list of edges and grow it so you get a connected â€śislandâ€ť of verts?

Hello @tfox_TD , sorry, I didnt explain well.
Thats what I want:

I have 2 separated edgeloops selected. I need to have from selection, each loop in one list.

Currently I have pairs of edges that are connected, for example:
[1,2] [2,3], [4,5] [5,6]

On the loop 1,2,3 , these edges are connected.
On the loop 4,5,6 too.
But the none of 1,2,3 is connected to none of 4,5,6.

I would need to have them separated like this: [1,2,3] and [4,5,6]

Let me know if I could explain better!
thanks!

Here, check out this post

Thereâ€™s still a bit of work to do with your data to make it work with this function, but itâ€™s like 98% there.

1 Like
``````xx = [[0, 11], [0, 16], [12, 8], [12, 9]]
vv = [set(x) for x in xx]

n = 0
while n < len(vv):
k = n + 1
while k < len(vv):
if bool(vv[n] & vv[k]):
vv[n] |= vv[k]
vv.pop(k)
else:
k += 1
n += 1

print(vv)

``````

`> Blockquote`

PS. if you have a long list of pairs and performance is critical, use collections.deque instead of list â€¦

2 Likes

@tfox_TD @denisT.MaxDoctor
thank you so much for these great orientation to you both.
its helping me on my script and on my learning as well.

thanks!!

hi @denisT.MaxDoctor I think it may doesnt work for more than 4 lists?
Im checking the other approach as well!
thanks!

you are rightâ€¦ it was a mistake in the previous algorithm â€¦ must work now:

``````from collections import deque
xx = xx = [ [19, 6], [14, 7], [22, 7], [14, 27], [19, 22], [39, 40], [40, 41], [41, 42], [42, 43],[43,44] ]

vv = deque(set(x) for x in xx)

n = 0
num = 0
while n < len(vv):
k = n + 1
while k < len(vv):
num += 1
if bool(vv[n] & vv[k]):
vv[n] |= vv[k]
del vv[k]
n = 0
else:
k += 1
n += 1

print(num, vv)
``````
1 Like

deleted for revisionâ€¦

after a revision:

``````from collections import deque
xx = [ [19, 6], [14, 7], [22, 7], [14, 27], [19, 22], [39, 40], [40, 41], [41, 42], [42, 43],[43,44] ]

vv = deque(set(x) for x in xx)

nn = None
while nn != len(vv):
nn = len(vv)
n = 0
while n < len(vv):
k = n + 1
while k < len(vv):
if bool(vv[n] & vv[k]):
vv[n] |= vv[k]
del vv[k]
else:
k += 1
n += 1

print(vv)
``````
2 Likes

What is this nonsense?

1 Like

She came, defecated and proudly walked off into the sunsetâ€¦
You were with us for such a short time, but you were remembered.
Rest in peace, Funny (D)Effective Managerâ€¦

Most likely the deleted posts were generated by an AI bot that someone is controlling of course. Unfortunately, there will be more and more of them, even on professional forums.

@denisT.MaxDoctor thank you so much, it works great!

frankly, the algorithm is not the fastestâ€¦ for large lists (10K+) something else will be needed â€¦ some â€śsmart sortingâ€ť. but nothing comes to mind yet.

1 Like

@denisT.MaxDoctor no worries! its very efficient for my goal, which is identify loops on low res meshes!

thanks a lot!

You can probably speed things up by pre-building a â€śneighborsâ€ť dictionary.
That way you donâ€™t need the loop `while k < len(vv):`. If you build a dictionary that stores which vertices neighbor any given vertex, then you can remove that loop and remove a bunch of expensive `set & set` checks and just directly access a list that has the next vertex.

Also, I donâ€™t think this is a good use-case for a deque. Theyâ€™re good for popping and inserting from the ends, but I suspect that deleting from the middle will have similar `O(n)` costs as a `list`. Efficiently deleting from the middle usually requires a linked list. But please test me, this is just an informed hunch.

Another hunch (this one is MUCH less informed) is that doing the `set & set` checks is slower than just doing the requisite 4 equality checks if you didnâ€™t turn the edge pairs into sets. Thatâ€™s because the set intersection must involve checking the hash equality and the object equality under-the-hood.

2 Likes

I have considered using a dictionary and gave it a try. Initially, it seemed like it could improve performance in the case of a single-choice loop without any branches. However, as soon as you need to account for branches, using sets is still the best approach. It seems â€śthe cure is worse than the diseaseâ€ť. Nevertheless, I plan to play more with this when I have free time.

1 Like

I had hoped deque would cleverly insert/erase elements to the left and right, but it doesnâ€™t seem to make much difference. However, some people suggest using it instead of listsâ€¦ maybeâ€¦ it needs to check

1 Like

I would also like to join the discussion, but there is a lack of initial data and dramatic details.
Abstract algorithms are of course fun and educational, but it would be interesting to know exactly what problem the author of the topic is trying to solve.
Because (outside the context of Maya), as a mathematical problem, similar problems have been thoroughly analyzed many times, for example, on Stackoverflow.
How was a list with pairs of indices for adjacent edges obtained?
How were edges-loops selections created?
How will the data found be used?
In the screenshot I see a selection consisting of two parallel non-intersecting edge loops on a regular rectangular plane.
If the problem is to differentiate the current allocation into separate lists of edge indices for individual loops, then such a problem can be effectively solved in other ways, using the tools of Maya itself.