检查pythonlis给出的兼容总订单

Question

我用的是IPython shell。在

假设我有两张单子

In [1]: L1 = [1,3,4,5,2]

In [2]: L2 = [1,3,5,5,1]

我想说L1和{}是兼容的，因为元素的递增顺序的索引生成的顺序是兼容的。在

也就是说，L1给出0<；4<；1<；2<；3；而L2给出{0,4}<；1<；{2,3}。（如果stackoverflow接受jsmath或MathJax，这会更容易，我很抱歉。）

编辑：正如下面指出的，这并不是精确地检查两个给定的元素是<；还是<；=在这两个元素中。我喜欢@Cosmologicon的例子，[1,2]和{}是兼容的，[1,1]和{}，但是{}和{}不兼容。我希望这能澄清我的意思。在

所以我想用一种方法来取两个列表，然后检查这两个列表给出的（不一定严格的）总顺序是否像这样兼容。这里有一个例子，他们没有。在

^{pr2}$

我希望很清楚L3给出的顺序是0<；1<；2<；3<；4；L4给出的顺序是0<；{1,3}<；2<；4，不兼容的是，虽然两个顺序中的1<；=3，但其中一个顺序是2<；3，而另一个顺序是3<；2。在

另一个更难的例子是[1,3,5,5,1]和{}是否兼容。非严格全序是{0,4}<；1<；{2,3}和0<；{1,2,4}<；3

就我的目的而言，限制在最大数总是len(list1)并且唯一可能的值是从1到{}和的情况下，其中list1总是这组整数的某种排列，但是如果有人发现更一般的东西，我自然不会抱怨。提前非常感谢！在

第一次发帖的免责声明：这是一个关于排序的问题：）我确实做了很多搜索，但实际上只找到了更多编程类型的问题，这些问题几乎总是关于排序或比较值；这有点微妙。事实上，它实际上是一个数学应用程序，所以对于这里的许多人来说，它似乎并不是“有用的”，尽管它对我来说非常有用。无论如何，我现在的技术水平已经超出了我现在的能力水平，尽管我希望有一天它会对我“显而易见”。我也不认为itertools中有任何关于这一点的东西，尽管我希望被证明是错误的。在

Answer 1

我认为，生成一个由列表元素和索引组成的元组列表的方法之一。然后可以按列表元素值和提取的索引对其进行排序。在

比如：

L1order = [t[1] for t in sorted(zip(L1, range(len(L1))))]
L2order = [t[1] for t in sorted(zip(L2, range(len(L2))))]
L1order == L2order

将其转换为函数应该很简单。在

Answer 2

我对尚的回答做了以下扩展。它考虑了两个值相同时所涉及的特殊事实。简单地对列表进行排序和比较可能会得出错误的结果。例如，如果列表1中的顺序是0<；1<；2，而列表2中的顺序是0<；1<；=2，那么对第二个列表排序可能会得到[0,1,2]和[0,2,1]的结果，在最后一种情况下，shang的方法将失败。这取决于排序例程的行为。在

import operator

def order_indexes(l):
    tmp = list(enumerate(l))
    tmp.sort(key=operator.itemgetter(1))
    return map(operator.itemgetter(0), tmp)

def are_compatible(l1, l2):
    # Order one list, retaining the indexes
    ordered = order_indexes(l1)
    # For each pair of indexes on the list
    for i in xrange(len(ordered) - 1):
        pair = (ordered[i], ordered[i + 1])
        # See if the pairs in the other list are compatible
        # If a1 <= b1 then a2 must be <= b2 
        if l2[pair[0]] > l2[pair[1]]:
            return False
    # If all pairs are compatible, then the lists are compatible
    return True

if __name__ == '__main__':
    l1 = [1,3,4,5,2]
    l2 = [1,3,5,5,1]
    l3 = [1,2,3,4,5]
    l4 = [1,2,4,2,5]
    print "L1 X L2 ",are_compatible(l1, l2)
    print "L2 X L1 ",are_compatible(l2, l1)
    print "L3 X L4 ",are_compatible(l3, l4)
    print "L4 X L3 ",are_compatible(l4, l3)

Answer 3

That is, L1 gives 0<4<1<2<3 while L2 gives 0<=4<1<2<=3. One can see that if two of these indices are <= each other in one list, that is true in both lists.

对不起，您在这里给出的compatible的定义与您的示例不匹配。在L2中，4<；=0，但L1中不是这样。我怀疑你想要给出的定义是：如果a<；b在一个列表中，那么a<；=b在另一个列表中。在

在这种情况下，以前的解决方案都不起作用。L1=[1,1]和L2=[2,1]应该兼容。在

不需要意识到任何解决方案都是可传递的。例如，如果L1=[1,2]，L2=[1,1]，L3=[2,1]，则L1与L2兼容，L2与L3兼容，但L1与L3不兼容。因此，任何检查从列表中计算的“排序”之间是否相等的解决方案都将失败。在

Thiago Chaves的解决方案没有这个问题，但是它在L1=[2,2,1]，L2=[2,1,1]时失败。这些应该是兼容的。在

编辑：如果效率不是一个大问题，这里有一个快速的O（N^2）解决方案，它只需测试每对数字：

def compat5(L1, L2):
    z = zip(L1, L2)
    return not any(j1<k1 and j2>k2 for j1,j2 in z for k1,k2 in z)