使相邻元素尽可能相同的数据排序算法

Question

我有一个（可能很大的）列表数据，包含三个小的非负整数元组，比如

data = [
    (1, 0, 5),
    (2, 4, 2),
    (3, 2, 1),
    (4, 3, 4),
    (3, 3, 1),
    (1, 2, 2),
    (4, 0, 3),
    (0, 3, 5),
    (1, 5, 1),
    (1, 5, 2),
]

我想对data中的元组进行排序，以便相邻的元组（data[I]和data[i1]）“尽可能相似”。

定义两个三元组的不相似性为它们之间不相等的元素的数量。例如。

• （0,1,2）vs.（0,1,2）：差异0.
• （0,1,2）vs.（0,1,3）：差异1.
• （0,1,2）vs.（0,2,1）：差异2.
• （0,1,2）vs.（3,4,5）：差异3.
• （0,1,2）vs.（2,0,1）：差异3.

问题：寻找数据排序的好算法是什么，它可以最小化所有相邻三元组之间的差异之和？

下面是一个计算两个三元组之间差异的函数：

def dissimilar(t1, t2):
    return sum(int(a != b) for a, b in zip(t1, t2))

这里有一个函数，它计算data的相加总差异，即我寻求最小化的数字：

def score(data):
    return sum(dissimilar(t1, t2) for t1, t2 in zip(data, data[1:]))

只需在数据的每个排列上运行score（），就可以解决这个问题：

import itertools
n_min = 3*len(data)  # some large number
for perm in itertools.permutations(data):
    n = score(perm)
    if n < n_min:
        n_min = n
        data_sorted = list(perm)
print(data_sorted, n_min)

虽然上面的方法有效，但它非常慢，因为我们显式地检查每个置换（导致O（N！））复杂性）。在我的机器上，当数据有10个元素时，上述过程大约需要20秒。

为了完整起见，以下是在给定示例data的情况下运行上述操作的结果：

data_sorted = [
    (1, 0, 5),
    (4, 0, 3),
    (4, 3, 4),
    (0, 3, 5),
    (3, 3, 1),
    (3, 2, 1),
    (1, 5, 1),
    (1, 5, 2),
    (1, 2, 2),
    (2, 4, 2),
]

使用n_min=15。请注意，还有几个分数为15的订单（10）。就我而言，这些都是等价的，我只想要其中一个。

在实践中，data的大小可能与10000一样大。

广受追捧的算法应该比O（N！），i、 e.在时间（和空间）上可能是多项式。

如果不存在这样的算法，我会对“近似解”感兴趣，即一种快速算法，它给出数据的排序，总分数很小，但不一定最小。其中一种算法是字典排序，即。

sorted(data)  # score 18

虽然我希望能做得更好。

Answer 1

这不是精确的算法，只是启发式的，但应该比简单的排序更好：

# you can sort first the data for lower total average score:
# data = sorted(data)

out = [data.pop(0)]
while data:
    idx, t = min(enumerate(data), key=lambda k: dissimilar(out[-1], k[1]))
    out.append(data.pop(idx))


print(score(out))

测试（100次重复，数据len（data）=1000）：

import random
from functools import lru_cache


def get_data(n=1000):
    f = lambda n: random.randint(0, n)
    return [(f(n // 30), f(n // 20), f(n // 10)) for _ in range(n)]


@lru_cache(maxsize=None)
def dissimilar(t1, t2):
    a, b, c = t1
    x, y, z = t2
    return (a != x) + (b != y) + (c != z)


def score(data):
    return sum(dissimilar(t1, t2) for t1, t2 in zip(data, data[1:]))


def lexsort(data):
    return sorted(data)


def heuristic(data, sort_data=False):
    data = sorted(data) if sort_data else data[:]
    out = [data.pop(0)]
    while data:
        idx, t = min(enumerate(data), key=lambda k: dissimilar(out[-1], k[1]))
        out.append(data.pop(idx))
    return out


N, total, total_lexsort, total_heuristic, total_heuristic2 = 100, 0, 0, 0, 0
for i in range(N):
    data = get_data()
    r0 = score(data)
    r1 = score(lexsort(data))
    r2 = score(heuristic(data))
    r3 = score(heuristic(data, True))
    print("original data", r0)
    print("lexsort", r1)
    print("heuristic", r2)
    print("heuristic with sorted", r3)

    total += r0
    total_lexsort += r1
    total_heuristic += r2
    total_heuristic2 += r3

print("total original data score", total)
print("total score lexsort", total_lexsort)
print("total score heuristic", total_heuristic)
print("total score heuristic(with sorted)", total_heuristic2)

打印：

...

total original data score 293682
total score lexsort 178240
total score heuristic 162722
total score heuristic(with sorted) 160384

Answer 2

这里有一个小的改进，不确定其复杂性，似乎是关于O（4ⁿ）。在不到一秒钟的时间内求解N=10。它对于大型案例来说太慢了，但对于测试其他解决方案可能很有用，因为它可以更快地计算测试输入的预期结果。

这个想法是，在N个三元组中，其中一个必须是中心。所以试着以每一个为中心。让half=N//2。然后，其他三元组的half必须位于中心的左侧，而N-1-half必须位于中心的右侧。尝试将所有拆分为左侧和右侧，并独立递归地解决它们。

我的助手函数不仅接受了data中的三元组，还接受了它所属的上下文：数据必须包含在head三元组和ail三元组之间（两者都可以是无），并且分数必须相应地计算。

import itertools

data = [
    (1, 0, 5),
    (2, 4, 2),
    (3, 2, 1),
    (4, 3, 4),
    (3, 3, 1),
    (1, 2, 2),
    (4, 0, 3),
    (0, 3, 5),
    (1, 5, 1),
    (1, 5, 2),
]

def dissimilar(t1, t2):
    if t1 and t2:
        a, b, c = t1
        x, y, z = t2
        return (a != x) + (b != y) + (c != z)
    return 0

def score(data):
    return sum(dissimilar(t1, t2) for t1, t2 in zip(data, data[1:]))

def solve(data):
    def solve(head, data, tail):
        if len(data) <= 3:
           perm = min(itertools.permutations(data),
                      key=lambda perm: score([head, *perm, tail]))
           return list(perm), score([head, *perm, tail])
        half = len(data) // 2
        result = result_score = None
        for center in list(data):
            data.remove(center)
            for left in itertools.combinations(data, half):
                left = set(left)
                right = data - left
                left, score_left = solve(head, left, center)
                right, score_right = solve(center, right, tail)
                if result_score is None or score_left + score_right < result_score:
                    result = [*left, center, *right]
                    result_score = score_left + score_right
            data.add(center)
        return result, result_score
    return solve(None, set(data), None)

result, result_score = solve(data)
print(result, result_score, score(result), sorted(result) == sorted(data))

Answer 3

不幸的是，这个问题是NP完全问题。你可以通过平面3-正则二部图上的哈密顿路径问题的简化来证明这一点，这也是NP完全的。

作为证明的概述：我们将为图的每个顶点创建一个3元组，这样，如果顶点相邻，对应的3元组对的相异性等于2，如果顶点不相邻，相异性等于3。每个顶点的3元组的成员将唯一地对应于顶点的关联边。

证明：
假设我们的输入是一个无向平面三次二部图G=（V，E），我们试图在其上找到哈密顿路径。我们可以在线性时间内找到边的3-着色。假设我们的三种边缘颜色是0、1、2。对于e中的每个边e，给它一个唯一的自然数标签L（e），这样L（e）mod 3就等于e的颜色。

我们可以用颜色0、1和2给边缘上色：

然后用最小自然数L（e）标记边缘，该自然数与mod 3的颜色有关：

对于V中的每个顶点v，创建一个3-TupleT=（t0， t1， t2），其中t0， t1， t2是入射到v的边的标签，余数分别等于0,1,2。请注意，每个边的标签出现在它所属的每个3-Tuple的相同索引处。在上述示例中，左上角的顶点将得到一个3-Tuple（0,1,29），最左边的顶点将得到一个3-Tuple（0,16,32）。

现在，在G中存在哈密顿路径，当且仅当存在具有不相似性和
2*（|V|-1）的3-元组排序时。这是因为3-元组排序具有不相似性和，当且仅当排序对应于G中的哈密顿路径。

参考文献和附录

证明中使用的简化来自于哈密顿路径问题的一个非常具体的版本。证明中使用的这类图（即平面、立方、二部图）的唯一性质是：

1. 图的色指数（边着色数）不得超过3。根据König的线着色定理，二部图的色指数等于最大顶点度，因此一个三次二部图就足够了
2. 边的3-着色必须在多项式时间内可计算。一般来说，寻找任意3边可着色图的边的3-着色是NP完全的。（事实上，通过尝试给线图的顶点着色，我们可以证明，根据Khanna等人的结果，找到3边可着色立方体图的4边着色是NP困难的。）。为了解决这个问题，我使用了Cole等人在O（E logd）时间内对二部多重图进行边着色的结果。这提供了一种在多项式（实际上是线性的）时间内构造二部图边上的3-着色的方法
3. 对于这类问题，哈密顿路径问题必须是NP难问题。关于平面图、and或立方体图、and或k-连通图、and或偶图等图的哈密顿圈或路径的NP完备性，有大量的结果拼凑而成。我可以引用的关于平面立方偶图哈密顿路径NP完备性的第一个直接证明是Munaro论文中的定理23，关于次三次无三角形图的线图。有可能是早期的参考文献表明了这一点；40年前，哈密顿圈问题的NP完备性已经被证明