python - 如何反转多维数组中的重复值

Question

我有一个像这样的字典(多维的？):

d = { 0: [3, 5], 1: [5, 7], 2: [4, 7], 3: [4, 3] }

我想在字典列表中找到任何重复的匹配位置 (0) 或 (1) 值，如果有重复则反转第二对匹配的数字。

字典会变成:

{ 0: [3, 5], 1: [5, 7], 2: [7, 4], 3: [4, 3] }

只有位置 (0) 会与位置 (0) 重复，只有位置 (1) 会与位置 (1) 重复(如果这有意义的话)。一系列中只能有一个重复项，所有数字都应在重复数据删除/翻转过程后链接在一起。下图说明:

[0 , 1] [1 , 2] [2 , 3] [3 , 0]

我正在尝试将所有相邻位置 (1) 与位置 (0) 进行匹配，因此这些值基本上是一个完整的圆圈(将其视为从一端连接到另一端的一系列线).我愿意使用 numpy 等任何可能有助于有效解决此问题的方法。这是另一个例子:

{ 'foo': [2, 9], 'bar': [3, 2], 'baz': [3, 9] } 

最终应该是:

[2, 9], [9, 3], [3, 2]

我试过很多东西，比如:

l = list(sorted(d.values()))

for i in range(0, len(l)):
    # now what the heck?

Answer 1

像这样形成链的一组对具有这样的属性，即每个元素在一对的第一个位置恰好出现一次，在第二个位置出现一次。如果您知道您的对中只有一个反转，您可以利用此属性:反转对中的第一个元素在第一个位置出现两次，而第二个元素根本没有出现在第一个位置。

想法是这样的:逐个检查对，并通过第一个元素跟踪每对。当我们看到第二对具有相同的第一个元素时，这两对中的一对必须是相反的——称这些候选者。当我们看到其中一个候选项的第二个元素是另一对的第一个元素时，我们知道那个候选项不是反转的那个，所以我们反转另一个。

此解决方案就地工作，这可能是也可能不是优势。转换为返回更正列表的列表很容易。它还有一个优点是它只通过对列表一次——在最坏的情况下。在大多数情况下，它可以在结束前停止。它比来自 recnac 的解决方案快大约七倍在我的测试中。

def fix_chain(pair_dict):
    first_to_pair = dict()
    this, that = None, None # candidates
    for pair in pair_dict.values():
        if pair[0] in first_to_pair: # found the collision
            this = pair
            that = first_to_pair[pair[0]]
        else:
            first_to_pair[pair[0]] = pair
        if this and this[1] in first_to_pair: # this is not reversed...
            that.reverse() # ... so that must be
            return
        if that and that[1] in first_to_pair: # that is not reversed...
            this.reverse() # ... so this must be
            return