We have n pairs and each pair has a common element with adjacent pair. Assume a cyclical group of pairs where nth pair is also adjacent to the first pair. Now, given n pairs, we want to output an array of size n that has 1s or 0s, depending on whether the pair must be flipped (or reoriented) or not. The goal is to flip the minimum number of pairs so as to have the pairs such that the common elements are next to each other.

For example,
 
Input: [(32,4),(4,1),(9,1),(9,16),(32,16)]

Output: [0,0,1,0,1]

such that upon flipping, we have [(32,4),(4,1),(1,9),(9,16),(16,32)] 

I am looking for an efficient solution, preferably using numpy.

CodePudding user response：

You can check if the first and second element for each pair is equal to the item in common between each consecutive pair:

inp    = [(32, 4), (4, 1), (9, 1), (9, 16), (32, 16)]
pairs  = [set(pair) for pair in inp]
common = [next(iter(one & two)) for one, two in zip(pairs, pairs[-1:]   pairs[:-1])]
out    = [int(comm != pair[0]) for comm, pair in zip(common, inp)]

[0, 0, 1, 0, 1] # output

You can do the final line using vectorization in numpy, but it's not really necessary