pythongraph-theorymulti-indexcombinatorics

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[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


Solution

  • 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),
        )
    ]