[Python] Using multi-indexing to find all combinations matching a certain pattern

I need to write an algorithm that takes N points, and outputs all the possible 3-stars and triangles that are formed by the points. Here's an example for clarification.

Let N = 4, then I have 4 choose 2 = 6 distances, the set

{(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}

We define a 3-star as 3 distances that all share 1 index. For example {(0,1),(1,2),(1,3)} is a star, but {(0,1),(1,2),(2,3)} is not. A triangle is defined as three distances where the first and second, second and third, and third and first pairs share an index, for example {(0,1),(1,2),(0,2)}, but not {(0,1),(1,2),(1,3)}.

I need to take N and output a list of all such 3-stars, and all triangles. They can be in the same list or in different lists for the output.

Is there a fast way to do this? I'm using python, so have access to the pandas multi-index which I think may be useful.

So far I've tried using a very naive approach, where I just loop 6 variables through 1 to NC2 and use an indicator function to pick out all the triangles. I've also managed to pick out the 3-stars using multi-index:

edges = list(itertools.combinations(range(N),2))
mi = pd.MultiIndex.from_tuples(edges)

# all 3 pairs share 1 index
for i in range(c):
core = mi
arr = np.bitwise_xor(mi.get_level_values(0) == core[0], mi.get_level_values(1) == core[1])
for (outer1, outer2) in itertools.combinations(mi[arr], 2):
if outer1[0] in outer2 or outer1[1] in outer2:
print(core, outer1, outer2)


But this duplicates each of the stars.

I'm sure there's a simple way to do this, but I just can't seem to get my head around it, so any help would be appreciated. Thanks

Continue reading...