1

GIVEN: a numpy array, a, where each successive pair of elements shares an element with some other pair in the row. Spaces have been added to emphasize the paired nature of the elements.

import numpy as np
 
a = np.array([[1,2,  1,3,  1,4,  6,1],
              [2,3,  2,4,  4,5,  8,5],
              [6,7,  1,2,  1,5,  2,6],
              [7,8,  2,3,  8,9,  3,4]])

The details of the shared elements will be important:
a[0] every pair shares an element (ie: 1) with every other pair
a[1] 1st pair shares with 2nd, 2nd with 3rd, 3rd with 4th
a[2] 1st pair shares with 4th, 2nd with 3rd and 4th
a[3] 1st pair shares with 3rd, 2nd with 4th

PROBLEM: I want to eliminate rows like a[3] whose PAIRS do NOT FORM a SINGLE CONNECTED NETWORK. The 1st and 3rd pairs of a[3], for example, have no way to 'get' to the 2nd or 4th pairs. The pairs in a[3] form two distinct disconnected networks, so a[3] should be eliminated.
The pairs in a[0], a[1], and a[2], by contrast, form a single connected network, so these rows are kept. (we can 'get' from any pair to any other pair)

I don't really have a good idea about how to approach this problem.

1 Answer 1

1

This is an interesting problem. Here is my approach:

import numpy as np

a = np.array([[1, 2, 1, 3, 1, 4, 6, 1],
              [2, 3, 2, 4, 4, 5, 8, 5],
              [6, 7, 1, 2, 1, 5, 2, 6],
              [7, 8, 2, 3, 8, 9, 3, 4],
              [1, 5, 4, 2, 3, 4, 5, 3]])


def is_network(row):
    npairs = row.size/2
    subnets = []

    for value in set(row):
        # find all the pair positions of the unique values in the row
        subnet = set(np.where(row == value)[0] // 2)
        if len(subnet) == npairs:
            # if a single value is present in all pairs, stop here
            return True
        else:
            # collect all the value-specific connections
            subnets.append(subnet)

    # look through all the subnets and try to build a network from
    # which you can access all pairs. since in a network where you can go
    # anywhere from anywhere else, it doesn't matter where you start.
    startnet = subnets[0]
    subnets.remove(startnet)
    i = 0
    while i < len(subnets) and len(startnet) < npairs:
        subnet = subnets[i]
        # whenever you can reach the subnet from the startnet (that is, 
        # when both subnets share at least one pair), add the pairs of the
        # subnet to the startnet. remove the subnet from the list of subnets 
        # because we don't need to loop over it again, and go back to 
        # the beginning of the list, because we might now be able to connect
        # the startnet subnets that we skipped previously. otherwise, continue
        # on with the next subnet.
        if startnet & subnet:
            startnet |= subnet
            subnets.remove(subnet)
            i = 0
        else:
            i += 1

    # if all pairs are included in the startnet, return True, else False
    return len(startnet) == npairs


mask = [is_network(r) for r in a]
print(mask)
a = a[mask]
4
  • So far, your solution seems to be working very well! Tomorrow I'll run it through some timing tests using larger arrays with 10 or 12 columns, then get back to you. Thanks for your contribution.
    – user109387
    Commented Dec 22, 2020 at 22:28
  • Great, you're welcome! Programming wise, I don't think there are any mistakes, I'm just not sure if there is a logical fallacy somewhere.
    – mapf
    Commented Dec 22, 2020 at 22:50
  • @user109387 ok so there was in deed one logical fallacy that the previous version did not take care of, which is that of the last row that I added to the matrix. my algorithm now also takes care of that and I am pretty confident now that it should work correctly for any case.
    – mapf
    Commented Dec 23, 2020 at 11:23
  • The code works very well, and is reasonably fast. Thanks for catching the logical fallacy! Nice work.
    – user109387
    Commented Dec 23, 2020 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.