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
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.
If you need more help, please keep asking questions.
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 …
@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)
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)
What is this nonsense?
Could you answer the questions asked and avoid flooding? … and keep your suggestions for your team.
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.
@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.
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.
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
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.
Additional context is also important:
How many loops can be allocated at the same time?
Can loops intersect?
What is polygeometry on which edges are distinguished?
Can there be additionally single edges (and/or other polycomponents/objects) that need to be ignored (or somehow taken into account)?
Other features and/or limitations?
Etc.
Sincerely.