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[i]
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
The stars are given by all permutations of 4 elements. The first element of the permutation is the centre of the star and the remaining 3 points are the outside of the star. You can eliminate the duplicates by ensuring that the last 3 elements of each permutation are in a given order (i.e. ascending order).
The triangles are given by all combinations of 3 elements. The triangle is formed by joining the first to the second then second to third and, finally, third back to the first element.
Like this:
from itertools import permutations, combinations
N = 4
stars = [{(a, b), (a, c), (a, d)} for a, b, c, d in permutations(range(N), 4) if b < c < d]
triangles = [{(a, b), (b, c), (c, a)} for a, b, c in combinations(range(N), 3)]
The stars are:
[{(0, 1), (0, 2), (0, 3)},
{(1, 0), (1, 2), (1, 3)},
{(2, 0), (2, 1), (2, 3)},
{(3, 0), (3, 1), (3, 2)}]
The triangles are:
[{(0, 1), (1, 2), (2, 0)},
{(0, 1), (1, 3), (3, 0)},
{(0, 2), (2, 3), (3, 0)},
{(1, 2), (2, 3), (3, 1)}]
Or, equivalently, if you want to use combinations to generate the stars:
stars = [
{(w, x), (w, y), (w, z)}
for a, b, c, d in combinations(range(N), 4)
for w, x, y, z in (
(a, b, c, d),
(b, a, c, d),
(c, a, b, d),
(d, a, b, c),
)
]