翻转/重定向具有公共元素的对，使相邻的对具有相邻的公共元素

Question

我们有n对，每对与相邻的对有一个公共元素。假设有一个循环组，其中第n对也与第1对相邻。现在，给定n对，我们想要输出一个大小为n的数组，其中有1或0，这取决于这对是否必须翻转(或重定向)。目标是翻转成对的最小数量，以使这些成对的公共元素彼此相邻。

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

我正在寻找一个有效的解决方案，最好使用numpy。

Answer 1

您可以检查每对的第一个和第二个元素是否等于每对连续的元素之间的共同项:

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

您可以在numpy中使用矢量化来完成最后一行，但实际上没有必要