对数据进行排序的算法，以使相邻元素尽可能相同
jmd*_*_dk 47 python algorithm optimization minimization time-complexity
我有一个（可能很大的）data小非负整数的三元组列表，例如
data = [\n (1, 0, 5),\n (2, 4, 2),\n (3, 2, 1),\n (4, 3, 4),\n (3, 3, 1),\n (1, 2, 2),\n (4, 0, 3),\n (0, 3, 5),\n (1, 5, 1),\n (1, 5, 2),\n]\n我想对其中的元组进行排序data，以便相邻元组（data[i]和data[i+1]）“尽可能相似”。
将两个三元组的不相似度定义为它们之间不相等的元素数量。例如
\n- \n
(0, 1, 2)对比(0, 1, 2)：差异0。 \n(0, 1, 2)对比(0, 1, 3)：差异1。 \n(0, 1, 2)对比(0, 2, 1)：差异2。 \n(0, 1, 2)对比(3, 4, 5)：差异3。 \n(0, 1, 2)对比(2, 0, 1)：差异3。 \n
问题：有什么好的算法可以找到data最小化所有相邻 3 元组之间的差异之和的排序？
一些代码
\n这是一个计算两个三元组之间差异的函数：
\ndef dissimilar(t1, t2):\n return sum(int(a != b) for a, b in zip(t1, t2))\n这是一个计算总相异度之和的函数data，即我寻求最小化的数字：
def score(data):\n return sum(dissimilar(t1, t2) for t1, t2 in zip(data, data[1:]))\nscore()这个问题可以通过简单地运行的每个排列来解决data：
import itertools\nn_min = 3*len(data) # some large number\nfor perm in itertools.permutations(data):\n n = score(perm)\n if n < n_min:\n n_min = n\n data_sorted = list(perm)\nprint(data_sorted, n_min)\n虽然上面的方法有效，但速度非常慢，因为我们显式检查每个排列（导致 O(N!) 复杂度）。在我的机器上，当有 10 个元素时，上述过程大约需要 20 秒data。
为了完整起见，这是运行上述示例的结果data：
data_sorted = [\n (1, 0, 5),\n (4, 0, 3),\n (4, 3, 4),\n (0, 3, 5),\n (3, 3, 1),\n (3, 2, 1),\n (1, 5, 1),\n (1, 5, 2),\n (1, 2, 2),\n (2, 4, 2),\n]\n和n_min = 15。请注意，其他几个排序（10总计）得分为15。就我的目的而言，这些都是等效的，我只想要其中之一。
最后的评论
\n实际上， 的大小data可能与所说的一样大10000。
受欢迎的算法应该击败 O(N!)，即可能是时间（和空间）上的多项式。
\n如果不存在这样的算法，我会对“近解”感兴趣，即一种快速算法，它给出的排序data较小但不一定是最小的总分。字典排序就是这样的一种算法，即
sorted(data) # score 18\n虽然我希望能够做得比这更好。
\n编辑（对已接受解决方案的评论）
\n我已经尝试了以下所有以代码形式给出的启发式解决方案（我没有尝试过，例如 Google OR-tools）。对于大型len(data)，我发现 Andrej Kesely 的解决方案既快速又给出了最好的结果。
这种方法背后的想法非常简单。数据元素（三元组）的排序列表是一一构建的。给定一些数据元素，下一个元素被选择为剩余（尚未排序的）数据中最相似的元素。
\n本质上，这解决了问题的本地化版本，我们只“向前看”，而不是对整个数据集进行全局优化。我们可以想象n未来的算法层次结构，每个算法相继提供更好（或至少同样好）的结果，但代价是更加昂贵。Andrej Kesely 的解决方案在这个层次结构中处于最低位置。最高点的算法，看len(data)，准确地解决了问题。
让我们满足于“向前看”，即 Andrej Kesely 的答案。这就为 a) 初始元素的选择，b) 当几个元素同样适合用作下一个元素（相同的相异性）时该怎么办。选择 中的第一个元素data作为初始元素以及具有最小相异性的元素的第一次出现，a) 和 b) 都是根据 中元素的原始顺序确定的data。正如 Andrej Kesely 指出的那样，这有助于 (lex) 排序data提前进行 (lex) 排序。
最后我采用了这个解决方案，但在几个方面进行了改进：
\n- \n
- 我尝试了 6 种初始排序的算法
data；lex 对列(0, 1, 2)、(2, 0, 1)、进行排序(1, 2, 0)，全部按升序和降序排列。 \n - 对于较大的
len(data)，算法对我来说变得太慢了。我怀疑它的规模是这样的O(n\xc2\xb2)。因此，我独立处理大小的数据块n_max，最终结果是连接不同排序的块。从一个块过渡到下一个块时，我们预计差异为 3，但如果我们保持n_max较大，则这一点并不重要。我跟去n_max = 1000。 \n
data.pop(idx)作为实现说明，可以通过不使用它本身来提高性能O(n)。相反，要么保持原始状态data并使用另一个数据结构来跟踪已使用的元素/索引，要么data[idx]在使用时替换为某些标记值。
kcs*_*red 26
不幸的是，这个问题是 NP 完全问题。您可以通过平面 3-正则二分图上的哈密顿路径问题的简化来证明这一点，这也是 NP 完全的。
\n作为证明的概述：我们将为图的每个顶点创建一个 3 元组，这样，如果顶点相邻，则对应的 3 元组对的相异性等于 2，如果顶点不相邻，则相异性等于 3邻近的。每个顶点的 3 元组的成员将唯一对应于顶点的关联边。
\n证明：
假设我们给出一个无向平面三次二部图作为输入，G = (V, E)我们试图在该图上找到哈密顿路径。我们可以在线性时间内找到边缘的 3 色。假设我们的三个边缘颜色是0, 1, 2。对于e中的每条边E，给它一个唯一的自然数标签L(e)，使其L(e) mod 3等于e\ 的颜色。
例如，对于这个立方平面二部图：\n
我们可以用颜色 0、1 和 2 为边缘着色：
\n
然后用尊重颜色 mod 3 的最小自然数 L(e) 标记边缘：
\n
v对于中的每个顶点V，创建一个 3 元组T = (t0, t1, t2)，其中是与余数分别等于的t0, t1, t2边的标签。请注意，每个边标签出现在其所属的每个 3 元组的相同索引处。在上面的示例中，左上角的顶点将获得一个 3-Tuple ，最左侧的顶点将获得一个 3-Tuple 。v0, 1, 2(0, 1, 29)(0, 16, 32)
现在，当且仅当存在具有相异和\nG的 3 元组的排序时，才存在哈密顿路径。这是因为当且仅当 3 元组的排序对应于 中的哈密顿路径时，该排序才具有相异和。2 * (|V| - 1)G
\n
参考文献和附录
\n证明中使用的约简来自哈密顿路径问题的一个极其具体的版本。证明中使用的此类图（即平面、立方、二分类）的唯一属性是：
\n- \n
- 图的色指数（边着色数）最多为 3。根据K\xc3\xb6nig\ 线着色定理的结果，二分图的色指数等于最大顶点度，因此立方二分图就足够了。 \n
- 边的三色必须可以在多项式时间内计算。一般来说，找到任意 3 边可着色图的边的 3 着色是NP 完全的。（事实上，通过尝试对线图的顶点进行着色，我们可以通过Khanna 等人的结果证明找到 3 边可着色立方图的 4 边着色是 NP 困难的。）。为了解决这个问题，我使用了 Cole 等人关于Edge-Coloring Bipartite Multigraphs in O(E log D) Time 的结果。这提供了一种在二分图上以多项式（实际上是线性）时间构造边上的 3 着色的方法。 \n
- 对于此类，哈密顿路径问题必须是 NP 困难的。对于平面、和/或三次、和/或 k 连接、和/或二部等图的哈密顿循环或路径的 NP 完整性，有大量结果拼凑而成。哈密顿路径 NP 完整性的第一个直接证明在平面三次二部图上，我可以引用 Munaro 论文《On line graphs of subcubic triangle-free graphs》中的定理 23 。早期的参考文献可能表明了这一点；该类哈密顿循环问题的 NP 完备性在四十年前就已被证明。 \n
- 嗯，我不相信你的减少能够满足他们的限制。他们说他们的数字“很小”，当我要求代码来生成实际的大输入时，他们说“n = 1000;” data = [(f(n//30), f(n//20), f(n//10)) for _ in range(n)]`。这意味着 1000 个元组中每个元组中的第一个值都是从 0 到 33 的整数。对于该 n，我认为您的值将上升到大约 1500。 (3认同)
- @KellyBundy 非常感谢；我错过了画图的那个边缘。你是对的，我的归约将具有 3 元组 1.5 倍的独特元素。只要每个槽的值范围至少是 3 元组数量的常数分数，问题就仍然是 NP 困难的。当唯一值的数量有不同的限制时，我不知道硬度。 (2认同)
- 为了“小”条目，每个三元组 $(t_0,t_1,t_2)=(3s_0, 3s_1+1, 3s_2+2)$ 可以替换为 $(s_0,s_1,s_2)$ (2认同)
- 它真的是NP-*完全*吗？我同意OP的问题肯定是NP难的，但我没有看到任何方法可以在多项式时间内检查给定的解决方案是否是最优的。 (2认同)
Kel*_*ndy 12
这是一个小改进，不确定复杂性，似乎约为 O(4 n )。在不到一秒的时间内解出 N=10。对于大型案例而言，它太慢了，但通过更快地计算测试输入的预期结果，对于测试其他解决方案可能很有用。
这个想法是，N 个三元组中，其中一个必须是中心。所以尝试以每个为中心。让half = N // 2。那么half其他三元组必须位于中心的左侧和N - 1 - half中心的右侧。尝试将所有拆分为左拆分和右拆分，并独立递归地解决它们。
我的辅助函数不仅接受三元组data，还接受它所属的上下文：数据必须包含在head三元组和tail三元组之间（两者都可以是None），并且必须相应地计算分数。
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))
And*_*ely 10
这不是精确的算法，只是启发式的，但应该比朴素排序更好：
# 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
也许也有用：下限。任何排序都是三元组链。链是一棵生成树。所以最低分数是一个下界。
\nAndrej Kesely 在 100 个随机输入上运行了他们的解决方案，得到了 160037 的总分。我在 100 个随机输入上运行了最小生成树。做了三次，总分分别是 153866、154040 和 153949。所以 Andrej 的 160037 看起来相当接近（比我的平均下限高 4.0%）。而且比他们的 178096 更接近lexsort并且比他们的 178096 距离（15.7% 以上）
代码（在线尝试！）：
\nimport random\n\ndef get_data(n=1000):\n f = lambda n: random.randint(0, n)\n return [(f(n // 30), f(n // 20), f(n // 10)) for _ in range(n)]\n\ndef dissimilar(t1, t2):\n a, b, c = t1\n x, y, z = t2\n return (a != x) + (b != y) + (c != z)\n\ndef mst_score(data):\n dist = dict.fromkeys(data, 3)\n dist[data[0]] = 0\n score = 0\n while dist:\n one = min(dist, key=dist.get)\n score += dist.pop(one)\n for other in dist:\n dist[other] = min(dist[other], dissimilar(one, other))\n return score\n\ntotal = 0\nfor i in range(100):\n data = get_data()\n score = mst_score(data)\n total += score\n print(score, total)\nAndrej Kesely 方法的直接替代方法，在同一测试中速度提高了约 30 倍。该方法通过始终附加与输出中最后一个最相似的剩余三元组来构建输出列表。大多数时候，剩下的三元组至少在一个位置与最后一个三元组相匹配。因此，我首先只检查至少在一个位置匹配的剩余三元组，而不是检查所有剩余的三元组的相似性。只有当失败时我才会检查所有剩余的三元组。我使用索引并打破与它们的相似性联系，因此我得到与 Andrej 相同的顺序。
我称一对为(spot, number)“标记”。例如，三元组(17, 3, 8)有标记(0, 17),(1, 3)和(2, 8)。这使我可以在这些位置查找与这些数字匹配的三元组。
from collections import defaultdict
def heuristic(data, sort_data=False):
data = sorted(data) if sort_data else data[:]
out = [data.pop(0)]
indexes = defaultdict(set)
for i, triple in enumerate(data):
for mark in enumerate(triple):
indexes[mark].add(i)
remain = set(range(len(data)))
while remain:
a, b, c = out[-1]
best = 4, None
for mark in enumerate(out[-1]):
for i in indexes[mark]:
x, y, z = data[i]
candidate = (a != x) + (b != y) + (c != z), i
if candidate < best:
best = candidate
i = best[1]
if i is None:
i = min(remain)
remain.remove(i)
t = data[i]
for pattern in enumerate(t):
indexes[pattern].remove(i)
out.append(t)
return out
如果我用这个替换循环，它的速度会快 35 倍for mark in enumerate(out[-1])，这不会比较我已经知道的匹配点：
for i in indexes[0, a]:
_, y, z = data[i]
candidate = (b != y) + (c != z), i
if candidate < best:
best = candidate
for i in indexes[1, b]:
x, _, z = data[i]
candidate = (a != x) + (c != z), i
if candidate < best:
best = candidate
for i in indexes[2, c]:
x, y, _ = data[i]
candidate = (a != x) + (b != y), i
if candidate < best:
best = candidate