排序数据以使相邻元素尽可能相同的算法
Algorithm for ordering data so that neighbor elements are as identical as possible
我有一个（可能很大的）列表data，其中包含小的非负整数的三元组，例如
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[i+1]）“尽可能相似”。
Define 两个三元组的dis相似度为它们之间不相等的元素个数。例如
(0, 1, 2) 与 (0, 1, 2)：差异 0。(0, 1, 2) 与 (0, 1, 3)：差异 1。(0, 1, 2) 与 (0, 2, 1)：差异 2。(0, 1, 2) 与 (3, 4, 5)：差异 3。(0, 1, 2) 与 (2, 0, 1)：差异 3。
问题：找到 data 排序的好算法是什么，它可以最小化所有相邻 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:]))
这个问题可以通过对 data:
的每个排列简单地 运行 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!) 复杂度）。在我的机器上，当 data 有 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!)，即可能是时间多项式（和 space）。
如果不存在这样的算法，我会对“接近解决方案”感兴趣，即一种快速算法，它给出 data 的排序，总分很小但不一定是最小的。一种这样的算法是 lexicographic sorting，即
sorted(data) # score 18
虽然我希望能够做得比这更好
编辑（对已接受解决方案的评论）
我已经尝试了以下所有作为代码给出的启发式解决方案（我没有尝试过，例如 Google OR 工具）。对于大 len(data)，我发现 Andrej Kesely 的解决方案既快速又给出了最好的结果。
这个方法背后的想法很简单。数据元素（三元组）的排序列表是一个接一个地建立起来的。给定一些数据元素，下一个元素被选为剩余（尚未排序的）数据中最相似的一个。
从本质上讲，这解决了我们只“向前看 一个”问题的本地化版本，而不是对整个数据集进行全局优化。我们可以想象一个算法的层次结构 n 展望未来，每个算法相继提供更好（或至少同样好）的结果，但代价是更加昂贵。 Andrej Kesely 的解决方案位于该层次结构的最低位置。最高处的算法，向前看len(data)，正好解决了问题。
让我们满足于“向前看 1”，即 Andrej Kesely 的回答。这为 a）初始元素的选择，b）当几个元素同样适合用作下一个元素（相同的差异）时该怎么做留下了空间。选取data中的第一个元素作为初始元素，第一次出现的相异性最小的元素，a)和b)均由data中元素的原始顺序确定。正如 Andrej Kesely 指出的那样，它有助于提前对 data 进行 (lex) 排序。
最后我采用了这个解决方案，但在几个方面进行了改进：
- 我尝试了
data 的 6 次初始排序的算法； lex 对列 (0, 1, 2)、(2, 0, 1)、(1, 2, 0) 进行排序，全部按升序和降序排列。
- 对于大
len(data)，算法对我来说太慢了。我怀疑它的规模像 O(n²)。因此，我独立处理大小为 n_max 的数据块，最终结果是将不同排序的数据块连接起来。从一个块过渡到下一个块，我们期望差异为 3，但如果我们保持 n_max 大，这并不重要。我选择 n_max = 1000.
作为实施说明，不使用 data.pop(idx) 可以提高性能，因为它本身就是 O(n)。相反，要么保留原来的 data 并使用另一个数据结构来跟踪使用了哪个 elements/indices，或者在使用时用一些标记值替换 data[idx]。
这里有一个小小的改进，不确定复杂度，好像是O(4n)。在不到一秒的时间内解决 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))
不幸的是，这个问题是NP-complete。您可以通过 Hamiltonian path problem on planar 3-regular bipartite graphs 的缩减来证明这一点，它也是 NP-complete.
作为证明的概述：我们将为图的每个顶点创建一个 3 元组，这样，如果顶点相邻，则对应的 3 元组对的相异度等于 2，相异度等于 3如果顶点不相邻。每个顶点的三元组的成员将唯一对应于顶点的入射边。
证明：
假设我们得到一个无向平面立方二分图 G = (V, E) 作为输入，我们试图在该图上找到哈密顿路径。我们可以在 linear time 中找到边缘的三色着色。假设我们的三个edge-colors是0, 1, 2。对于E中的每条边e，给它一个唯一的自然数标签L(e)，使得L(e) mod 3等于e的颜色。
例如，对于这个立方平面二分图：
我们可以用颜色 0、1 和 2 给边上色：
然后用尊重颜色的最小自然数 L(e) 标记边缘 mod 3:
对于V中的每个顶点v，创建一个三元组T = (t0, t1, t2)，其中t0, t1, t2是与v关联的边的标签余数分别等于 0, 1, 2。请注意，每个边缘标签出现在它所属的每个三元组的相同索引处。在上面的例子中，左上角的顶点将得到一个三元组 (0, 1, 29) 而 left-most 顶点将得到一个三元组 (0, 16, 32).
现在，在 G 中存在哈密顿路径当且仅当存在具有相异和
的 3 元组排序时
2 * (|V| - 1)。这是因为当且仅当排序对应于 G.
中的哈密顿路径时，三元组的排序才具有相异和
参考文献和附录
证明中使用的归约来自哈密顿路径问题的一个极其具体的版本。证明中使用的此 class 图（即平面图、立方图、二分图 class）的唯一属性是：
- 图的色度指数（边着色数）最多为3。根据König's line coloring theorem的结果，二分图的色度指数等于最大顶点度，所以三次二分图就足够了。
- 边缘的三色必须在多项式时间内可计算。通常，找到任意 3-edge-colorable 图的边的 3 着色是 NP-complete. (In fact, by trying to color the vertices of the line graph, we can show it's NP-hard to find a 4-edge-coloring of a 3-edge-colorable cubic graph with this result by Khanna et al.). To fix this, I used a result by Cole et al on Edge-Coloring Bipartite Multigraphs in O(E log D) Time。这提供了一种在我们的二部图上以多项式（实际上是线性的）时间在边上构造 3 着色的方法。
- 对于这个 class，哈密顿路径问题必须 NP-hard。对于平面图、和/或立方图、和/或k-connected和/或二部图等的哈密顿循环或路径，有大量关于 NP-completeness 的结果拼凑而成。第一个直接证明 NP-complete我可以引用的平面三次二分图上哈密顿路径的性是 Munaro 论文中的定理 23，On line graphs of subcubic triangle-free graphs。较早的参考资料可能表明了这一点；关于 class 的哈密顿循环问题的 NP-complete 性在四十年前就得到了证明。
这不是精确算法，只是启发式算法，但应该比朴素排序更好：
# 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))
测试（使用数据 len(data)=1000 重复 100 次）：
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
也许也有用：下限。任何排序都是三元组的链。链是生成树。所以minimum生成树的分数是一个下界。
Andrej Kesely 运行 他们在 100 运行dom 输入上的解决方案得到了 160037 的总分。我在 100 运行dom 输入上 运行 最小生成树。做了 3 次，总分分别是 153866、154040 和 153949。所以 Andrej 的 160037 看起来相当接近（比我的平均下限高 4.0%）。并且比 lexsort 的 178096 更接近（高于 15.7%）。
代码(Try it online!):
import random
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)]
def dissimilar(t1, t2):
a, b, c = t1
x, y, z = t2
return (a != x) + (b != y) + (c != z)
def mst_score(data):
dist = dict.fromkeys(data, 3)
dist[data[0]] = 0
score = 0
while dist:
one = min(dist, key=dist.get)
score += dist.pop(one)
for other in dist:
dist[other] = min(dist[other], dissimilar(one, other))
return score
total = 0
for i in range(100):
data = get_data()
score = mst_score(data)
total += score
print(score, total)
如果对于每一对（子集，最后一个元素）你找到答案来放置子集中的所有元素以便最后一个元素固定，你可以在 O(2ⁿ·n²) 中完成。您可以递归地执行此操作（迭代前一个元素），注意不要多次计算相同的状态（记忆）
你生成测试数据的代码是这样的：
def f(n):
return random.randint(0, n)
n = 10_000
data = [(f(n//30), f(n//20), f(n//10)) for _ in range(n)]
我的想法是简单地找到要排序的每个项目中列（或字段）的最佳顺序，然后看看结果如何。
我推测每列中数字的标准偏差可能对整体相似性产生有益影响，即如果第三列中的数字不多，那么可能首先对第三列值进行排序以保持它们放在一起，以及当连续的第三列值相同时，对哪一列进行排序以打破平局的类似考虑，等等...
我发现 10_000 项目的随机排序给出了非常低的相似性。按 field/column 的顺序排序，标准偏差最小，大多数给出更好的相似性。按任何列顺序排序看起来比随机排序要好。
代码
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 16 10:33:41 2022
@author: paddy3118
"""
import random
from typing import List, Tuple
import pandas as pd
def f(n):
return random.randint(0, n)
def stddev_mean(lst: List[int]) -> Tuple[float, float]:
"Standard deviation of numbers in lst, mean."
sm = sum(lst)
sm2 = sum(i**2 for i in lst)
n = len(lst)
return ((sm2 - sm**2 / n) / n)**0.5, sm / n
def similarity(d) -> int:
"Compare successive 3-tuples for similarity - higher is better"
return sum(sum((field0 == field1) for field0, field1 in zip(d0, d1))
for d0, d1 in zip(d, d[1:]))
#%% Test data
data = [ # SIMILARITY in fields of seccessive records
(0, 1, 2),
(2, 4, 2), # 1
(3, 2, 1), # 0
(4, 3, 4), # 0
(3, 3, 1), # 1
(1, 2, 2), # 0
(4, 0, 3), # 0
(0, 3, 5), # 0
(1, 5, 1), # 0
(1, 5, 2), # 2
] # Sum = 4
assert similarity(data) == 4
#%% Randomised data
print("NOTE: Similarity figures are better when higher.\n")
n = 10_000
data = [(f(n//30), f(n//20), f(n//10)) for _ in range(n)]
print(f"Random generation of {n} items has similarity of = {similarity(data)}")
field_stddev = [(i, stddev_mean([datum[i] for datum in data])[0])
for i in range(len(data[0]))]
print(f"{field_stddev = }")
#%% Order by increasing stddeviation field
index_by_inc_dev = [ind for ind, _ in
sorted(field_stddev, key=lambda x: x[1])]
print(f"\nField indices by INcreasing stddev of tuple field values = {index_by_inc_dev}")
sort_by_field_of_inc_dev = sorted(data,
key=lambda d:[d[i]
for i in index_by_inc_dev])
print(f"{similarity(sort_by_field_of_inc_dev) = :,}")
assert set(sort_by_field_of_inc_dev) == set(data), "Whoops, data lost in sort??"
#%% Order by increasing stddeviation field
print(f"\nField indices by DEcreasing stddev of tuple field values = {index_by_inc_dev[::-1]}")
sort_by_field_of_dec_dev = sorted(data,
key=lambda d:[d[i]
for i in index_by_inc_dev[::-1]])
print(f"{similarity(sort_by_field_of_dec_dev) = :,}")
assert set(sort_by_field_of_dec_dev) == set(data), "Whoops, data lost in sort??"
#%%
print("\n Same data, random sorts, gives these similarity values:")
dcopy = data.copy()
for i in range(10):
print(f" Random similarity({i}) = {similarity(dcopy):,}")
random.shuffle(dcopy)
输出
NOTE: Similarity figures are better when higher.
Random generation of 10000 items has similarity of = 55
field_stddev = [(0, 96.04927579341764), (1, 145.8145251033312), (2, 288.84656085582884)]
Field indices by INcreasing stddev of tuple field values = [0, 1, 2]
similarity(sort_by_field_of_inc_dev) = 9,949
Field indices by DEcreasing stddev of tuple field values = [2, 1, 0]
similarity(sort_by_field_of_dec_dev) = 9,135
Same data, random sorts, gives these similarity values:
Random similarity(0) = 55
Random similarity(1) = 61
Random similarity(2) = 54
Random similarity(3) = 60
Random similarity(4) = 68
Random similarity(5) = 55
Random similarity(6) = 56
Random similarity(7) = 58
Random similarity(8) = 56
Random similarity(9) = 63
一个相当不错的近似（模拟退火方式）解：
从项目的任意（或随机）排列开始。可选：选择 N 个随机排列（比如 10 或 100）并从总误差最低的排列开始，丢弃其他排列。
选择两个不同的随机索引并交换这些索引处的项目，如果它会减少总误差（你可以通过计算“之前”和“之后”列表的总误差来直接做到这一点，但是您也可以通过交换和不交换来检查项目 i-1, i, i+1 和 j-1, j, j+1；所有其他导致错误的因素保持不变。
重复上一步，直到您选择某个停止条件，可以是以下一个或多个：
- 您达到了一些预定义的迭代次数或执行时间限制，
- 总误差低于某个阈值，
- 过去 N 次迭代中“成功交换”的百分比低于阈值，
- 您进行了 N 次迭代而没有成功交换。
这改进了我之前的答案，并且还表明按列排序的列顺序是通过增加该列中数字的 std-deviations 确实 给出更好的结果结果。
一个额外的算法采用最佳排序并交换相邻行（如果这增加了整体相似性）直到没有更多的相邻交换改进结果。
代码
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 17 07:30:23 2022
@author: paddy
"""
import random
from itertools import permutations
from typing import List, Tuple
DType = List[Tuple[int, int, int]]
def randomised_data_gen(n: int) -> DType:
def f(n):
return random.randint(0, n)
return [(f(n // 30), f(n // 20), f(n // 10)) for _ in range(n)]
def stddev_mean(lst: List[int]) -> Tuple[float, float]:
"Standard deviation of numbers in lst, mean."
sm = sum(lst)
sm2 = sum(i**2 for i in lst)
n = len(lst)
return ((sm2 - sm**2 / n) / n)**0.5, sm / n
def similarity(d: DType) -> int:
"Compare successive 3-tuples for similarity - higher is better"
return sum(sum((col0 == col1) for col0, col1 in zip(d0, d1)) for d0, d1 in zip(d, d[1:]))
def sort_by_column(data: DType, column_index: Tuple[int]) -> DType:
return sorted(data, key=lambda d: [d[i] for i in column_index])
def similarity_when_randomized(data: DType, n: int = 10) -> None:
dcopy = data.copy()
sims = ", ".join([f"{similarity(dcopy):_}", random.shuffle(dcopy)][0] for _ in range(n))
print(f" Same data random sorts gives similarity values: {sims}")
#%% Test data
def test1():
data = [ # SIMILARITY in columns of sucessive records
(0, 1, 2),
(2, 4, 2), # 1
(3, 2, 1), # 0
(4, 3, 4), # 0
(3, 3, 1), # 1
(1, 2, 2), # 0
(4, 0, 3), # 0
(0, 3, 5), # 0
(1, 5, 1), # 0
(1, 5, 2), # 2
] # Sum = 4
assert similarity(data) == 4
test1()
#%% Randomised data
print("NOTE: Similarity figures are better when higher.\n")
n = 10_000
data = randomised_data_gen(n)
print(f"Random generation of {n} items has similarity of = {similarity(data)}")
similarity_when_randomized(data, 10)
col_stddev = [(i, stddev_mean([datum[i] for datum in data])[0]) for i in range(len(data[0]))]
print(f"\n(Column_index, Standard_deviation) of each column of numbers: {col_stddev}")
#%% Order by increasing stddeviation column
index_by_inc_dev = [ind for ind, _ in sorted(col_stddev, key=lambda x: x[1])]
#%% Sort by columns
def score_all_column_orders(data: DType) -> Tuple[List[Tuple[int, Tuple[int, int, int]]], DType]:
"Print and return similarity scores for sorting data by all column orders, best first AND the best sort of data"
sim_by_column_sort = [(similarity(sort_by_column(data, column_order)), column_order)
for column_order in permutations(range(len(data[0])))]
sim_by_column_sort.sort(reverse=True) # Highest similarity first
print("\nSimilarity when sorting by all column orders:")
print(" SIMILARITY SORT_COLUMN_ORDER")
for sim, col in sim_by_column_sort:
col = list(col)
if col == index_by_inc_dev[::-1]:
comment = " (by DEcreasing std-dev)"
elif col == index_by_inc_dev:
comment = " (by INcreasing std-dev)"
else:
comment = ""
print(f" {sim:>10_} {col}{comment}")
return sim_by_column_sort, sort_by_column(data, sim_by_column_sort[0][1])
_, best_by_col_sort = score_all_column_orders(data)
score = best_score = similarity(best_by_col_sort)
#%% Swap with next row
print("\nNeighbourly swaps:")
twizzled = best_by_col_sort.copy()
while True:
swaps = 0
for i in range(1, len(twizzled) - 2):
#breakpoint()
i_window = [ twizzled[x] for x in [i-1, i, i+1, i+2]]
i_swap = [ twizzled[x] for x in [i-1, i+1, i, i+2]]
if similarity(i_swap) > similarity(i_window):
twizzled[i], twizzled[i+1] = twizzled[i+1], twizzled[i]
swaps += 1
if swaps == 0:
break
print(f" Neighbour {swaps = } New similarity = {similarity(twizzled)}")
示例输出
NOTE: Similarity figures are better when higher.
Random generation of 10000 items has similarity of = 70
Same data random sorts gives similarity values: 70, 57, 65, 57, 51, 61, 64, 56, 63, 50
(Column_index, Standard_deviation) of each column of numbers: [(0, 96.5443987139596), (1, 145.326873357098), (2, 288.69842362782305)]
Similarity when sorting by all column orders:
SIMILARITY SORT_COLUMN_ORDER
9_978 [0, 1, 2] (by INcreasing std-dev)
9_829 [0, 2, 1]
9_802 [1, 0, 2]
9_638 [1, 2, 0]
9_160 [2, 0, 1]
9_142 [2, 1, 0] (by DEcreasing std-dev)
Neighbourly swaps:
Neighbour swaps = 12 New similarity = 9990
采用随机组合优化算法，如tabu search, a genetic algorithm, or simulated annealing。根据我的经验，我已经订购了降低效率的替代品。
所有这些都涉及从一个或多个随机解决方案开始，然后通过随机扰动和一种决定保留哪些解决方案的方法在连续迭代中改进结果。 objective 函数（在您的情况下是完全不同）会指导您进行改进。对于您提到的数字，几千次迭代后您将获得接近最优的解决方案。
也许这可以帮到你。这是一种你必须验证的方法，我没有时间开发它，但我认为它是可行的。
如果元素列表是有序的，它的排序将是微不足道的：线性的。将每个元素与下一个元素进行比较就足够了。
如果只有一些元素放错了位置但接近它们的正确位置，排序会稍微慢一些，但也很快。大多数时候，每个元素都会与下一个元素进行比较，有些元素需要进行一些额外的比较才能放置到位。
基于以上，我的做法是轻松得到一个比较有序的列表。为此，根据元素的线性回归进行排序就足够了（如果我没记错的话）。我将在二维中解释它（元素具有 2 个值而不是 3 个），因为它更简单，但将它传递到 3 个维度，正如你在问题中所问的，并不复杂。
您对所有元素进行初始 运行 并计算回归线。
然后，计算回归线变为 Y=0 所需的旋转并将该旋转应用于您的点。这允许您 运行 按顺序从左到右遍历点。该顺序就是您用作第一个排序顺序的顺序。
显然，两个相邻的点可能不是彼此最接近的，但很少会有更接近的点，因此最终排序将始终是局部的并且需要很少的移动。
也就是说，我们使用回归线作为元素应该具有的最终位置的近似值。很明显，在回归线上相距较远的两个元素（运行ning 从一端到另一端）也相距较远，这使我们能够以接近最佳的方式排列它们。
这迫使我们进行几次计算，这些计算不是很复杂，但比每对元素之间的比较复杂得多。也就是说，比较少的情况下，这种方法的成本更高，但在某一点上，这种方法比在元素之间进行大量比较要好。
要将其移动到 3 维（并使用您需要的 3 个分量），您必须使用 3D 回归线并获得 3 维旋转矩阵。其他类似。
drop-in 替代 Andrej Kesely 的方法，在同一测试中速度提高了大约 30 倍。该方法通过始终在输出中附加与最后一个最相似的剩余三元组来构建输出列表。大多数时候，剩下的三元组至少在一个位置上与最后一个匹配。因此，我没有检查 all 剩余的三元组的相似性，而是首先只检查在至少一个位置匹配的剩余三元组。只有当失败时，我才会检查所有剩余的三元组。我使用索引并打破与它们的相似关系，所以我得到与 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
如果我用这个替换 for mark in enumerate(out[-1]) 循环，它会快大约 35 倍，这不会比较我已经知道的匹配点：
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
我有一个（可能很大的）列表data，其中包含小的非负整数的三元组，例如
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[i+1]）“尽可能相似”。
Define 两个三元组的dis相似度为它们之间不相等的元素个数。例如
(0, 1, 2)与(0, 1, 2)：差异0。(0, 1, 2)与(0, 1, 3)：差异1。(0, 1, 2)与(0, 2, 1)：差异2。(0, 1, 2)与(3, 4, 5)：差异3。(0, 1, 2)与(2, 0, 1)：差异3。
问题：找到 data 排序的好算法是什么，它可以最小化所有相邻 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:]))
这个问题可以通过对 data:
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!) 复杂度）。在我的机器上，当 data 有 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!)，即可能是时间多项式（和 space）。
如果不存在这样的算法，我会对“接近解决方案”感兴趣，即一种快速算法，它给出 data 的排序，总分很小但不一定是最小的。一种这样的算法是 lexicographic sorting，即
sorted(data) # score 18
虽然我希望能够做得比这更好
编辑（对已接受解决方案的评论）
我已经尝试了以下所有作为代码给出的启发式解决方案（我没有尝试过，例如 Google OR 工具）。对于大 len(data)，我发现 Andrej Kesely 的解决方案既快速又给出了最好的结果。
这个方法背后的想法很简单。数据元素（三元组）的排序列表是一个接一个地建立起来的。给定一些数据元素，下一个元素被选为剩余（尚未排序的）数据中最相似的一个。
从本质上讲，这解决了我们只“向前看 一个”问题的本地化版本，而不是对整个数据集进行全局优化。我们可以想象一个算法的层次结构 n 展望未来，每个算法相继提供更好（或至少同样好）的结果，但代价是更加昂贵。 Andrej Kesely 的解决方案位于该层次结构的最低位置。最高处的算法，向前看len(data)，正好解决了问题。
让我们满足于“向前看 1”，即 Andrej Kesely 的回答。这为 a）初始元素的选择，b）当几个元素同样适合用作下一个元素（相同的差异）时该怎么做留下了空间。选取data中的第一个元素作为初始元素，第一次出现的相异性最小的元素，a)和b)均由data中元素的原始顺序确定。正如 Andrej Kesely 指出的那样，它有助于提前对 data 进行 (lex) 排序。
最后我采用了这个解决方案，但在几个方面进行了改进：
- 我尝试了
data的 6 次初始排序的算法； lex 对列(0, 1, 2)、(2, 0, 1)、(1, 2, 0)进行排序，全部按升序和降序排列。 - 对于大
len(data)，算法对我来说太慢了。我怀疑它的规模像O(n²)。因此，我独立处理大小为n_max的数据块，最终结果是将不同排序的数据块连接起来。从一个块过渡到下一个块，我们期望差异为 3，但如果我们保持n_max大，这并不重要。我选择n_max = 1000.
作为实施说明，不使用 data.pop(idx) 可以提高性能，因为它本身就是 O(n)。相反，要么保留原来的 data 并使用另一个数据结构来跟踪使用了哪个 elements/indices，或者在使用时用一些标记值替换 data[idx]。
这里有一个小小的改进，不确定复杂度，好像是O(4n)。在不到一秒的时间内解决 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))
不幸的是，这个问题是NP-complete。您可以通过 Hamiltonian path problem on planar 3-regular bipartite graphs 的缩减来证明这一点，它也是 NP-complete.
作为证明的概述：我们将为图的每个顶点创建一个 3 元组，这样，如果顶点相邻，则对应的 3 元组对的相异度等于 2，相异度等于 3如果顶点不相邻。每个顶点的三元组的成员将唯一对应于顶点的入射边。
证明：
假设我们得到一个无向平面立方二分图 G = (V, E) 作为输入，我们试图在该图上找到哈密顿路径。我们可以在 linear time 中找到边缘的三色着色。假设我们的三个edge-colors是0, 1, 2。对于E中的每条边e，给它一个唯一的自然数标签L(e)，使得L(e) mod 3等于e的颜色。
例如，对于这个立方平面二分图：
我们可以用颜色 0、1 和 2 给边上色：
然后用尊重颜色的最小自然数 L(e) 标记边缘 mod 3:
对于V中的每个顶点v，创建一个三元组T = (t0, t1, t2)，其中t0, t1, t2是与v关联的边的标签余数分别等于 0, 1, 2。请注意，每个边缘标签出现在它所属的每个三元组的相同索引处。在上面的例子中，左上角的顶点将得到一个三元组 (0, 1, 29) 而 left-most 顶点将得到一个三元组 (0, 16, 32).
现在，在 G 中存在哈密顿路径当且仅当存在具有相异和
的 3 元组排序时
2 * (|V| - 1)。这是因为当且仅当排序对应于 G.
参考文献和附录
证明中使用的归约来自哈密顿路径问题的一个极其具体的版本。证明中使用的此 class 图（即平面图、立方图、二分图 class）的唯一属性是：
- 图的色度指数（边着色数）最多为3。根据König's line coloring theorem的结果，二分图的色度指数等于最大顶点度，所以三次二分图就足够了。
- 边缘的三色必须在多项式时间内可计算。通常，找到任意 3-edge-colorable 图的边的 3 着色是 NP-complete. (In fact, by trying to color the vertices of the line graph, we can show it's NP-hard to find a 4-edge-coloring of a 3-edge-colorable cubic graph with this result by Khanna et al.). To fix this, I used a result by Cole et al on Edge-Coloring Bipartite Multigraphs in O(E log D) Time。这提供了一种在我们的二部图上以多项式（实际上是线性的）时间在边上构造 3 着色的方法。
- 对于这个 class，哈密顿路径问题必须 NP-hard。对于平面图、和/或立方图、和/或k-connected和/或二部图等的哈密顿循环或路径，有大量关于 NP-completeness 的结果拼凑而成。第一个直接证明 NP-complete我可以引用的平面三次二分图上哈密顿路径的性是 Munaro 论文中的定理 23，On line graphs of subcubic triangle-free graphs。较早的参考资料可能表明了这一点；关于 class 的哈密顿循环问题的 NP-complete 性在四十年前就得到了证明。
这不是精确算法，只是启发式算法，但应该比朴素排序更好：
# 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))
测试（使用数据 len(data)=1000 重复 100 次）：
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
也许也有用：下限。任何排序都是三元组的链。链是生成树。所以minimum生成树的分数是一个下界。
Andrej Kesely 运行 他们在 100 运行dom 输入上的解决方案得到了 160037 的总分。我在 100 运行dom 输入上 运行 最小生成树。做了 3 次，总分分别是 153866、154040 和 153949。所以 Andrej 的 160037 看起来相当接近（比我的平均下限高 4.0%）。并且比 lexsort 的 178096 更接近（高于 15.7%）。
代码(Try it online!):
import random
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)]
def dissimilar(t1, t2):
a, b, c = t1
x, y, z = t2
return (a != x) + (b != y) + (c != z)
def mst_score(data):
dist = dict.fromkeys(data, 3)
dist[data[0]] = 0
score = 0
while dist:
one = min(dist, key=dist.get)
score += dist.pop(one)
for other in dist:
dist[other] = min(dist[other], dissimilar(one, other))
return score
total = 0
for i in range(100):
data = get_data()
score = mst_score(data)
total += score
print(score, total)
如果对于每一对（子集，最后一个元素）你找到答案来放置子集中的所有元素以便最后一个元素固定，你可以在 O(2ⁿ·n²) 中完成。您可以递归地执行此操作（迭代前一个元素），注意不要多次计算相同的状态（记忆）
你生成测试数据的代码是这样的：
def f(n):
return random.randint(0, n)
n = 10_000
data = [(f(n//30), f(n//20), f(n//10)) for _ in range(n)]
我的想法是简单地找到要排序的每个项目中列（或字段）的最佳顺序，然后看看结果如何。
我推测每列中数字的标准偏差可能对整体相似性产生有益影响，即如果第三列中的数字不多，那么可能首先对第三列值进行排序以保持它们放在一起，以及当连续的第三列值相同时，对哪一列进行排序以打破平局的类似考虑，等等...
我发现 10_000 项目的随机排序给出了非常低的相似性。按 field/column 的顺序排序，标准偏差最小，大多数给出更好的相似性。按任何列顺序排序看起来比随机排序要好。
代码
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 16 10:33:41 2022
@author: paddy3118
"""
import random
from typing import List, Tuple
import pandas as pd
def f(n):
return random.randint(0, n)
def stddev_mean(lst: List[int]) -> Tuple[float, float]:
"Standard deviation of numbers in lst, mean."
sm = sum(lst)
sm2 = sum(i**2 for i in lst)
n = len(lst)
return ((sm2 - sm**2 / n) / n)**0.5, sm / n
def similarity(d) -> int:
"Compare successive 3-tuples for similarity - higher is better"
return sum(sum((field0 == field1) for field0, field1 in zip(d0, d1))
for d0, d1 in zip(d, d[1:]))
#%% Test data
data = [ # SIMILARITY in fields of seccessive records
(0, 1, 2),
(2, 4, 2), # 1
(3, 2, 1), # 0
(4, 3, 4), # 0
(3, 3, 1), # 1
(1, 2, 2), # 0
(4, 0, 3), # 0
(0, 3, 5), # 0
(1, 5, 1), # 0
(1, 5, 2), # 2
] # Sum = 4
assert similarity(data) == 4
#%% Randomised data
print("NOTE: Similarity figures are better when higher.\n")
n = 10_000
data = [(f(n//30), f(n//20), f(n//10)) for _ in range(n)]
print(f"Random generation of {n} items has similarity of = {similarity(data)}")
field_stddev = [(i, stddev_mean([datum[i] for datum in data])[0])
for i in range(len(data[0]))]
print(f"{field_stddev = }")
#%% Order by increasing stddeviation field
index_by_inc_dev = [ind for ind, _ in
sorted(field_stddev, key=lambda x: x[1])]
print(f"\nField indices by INcreasing stddev of tuple field values = {index_by_inc_dev}")
sort_by_field_of_inc_dev = sorted(data,
key=lambda d:[d[i]
for i in index_by_inc_dev])
print(f"{similarity(sort_by_field_of_inc_dev) = :,}")
assert set(sort_by_field_of_inc_dev) == set(data), "Whoops, data lost in sort??"
#%% Order by increasing stddeviation field
print(f"\nField indices by DEcreasing stddev of tuple field values = {index_by_inc_dev[::-1]}")
sort_by_field_of_dec_dev = sorted(data,
key=lambda d:[d[i]
for i in index_by_inc_dev[::-1]])
print(f"{similarity(sort_by_field_of_dec_dev) = :,}")
assert set(sort_by_field_of_dec_dev) == set(data), "Whoops, data lost in sort??"
#%%
print("\n Same data, random sorts, gives these similarity values:")
dcopy = data.copy()
for i in range(10):
print(f" Random similarity({i}) = {similarity(dcopy):,}")
random.shuffle(dcopy)
输出
NOTE: Similarity figures are better when higher.
Random generation of 10000 items has similarity of = 55
field_stddev = [(0, 96.04927579341764), (1, 145.8145251033312), (2, 288.84656085582884)]
Field indices by INcreasing stddev of tuple field values = [0, 1, 2]
similarity(sort_by_field_of_inc_dev) = 9,949
Field indices by DEcreasing stddev of tuple field values = [2, 1, 0]
similarity(sort_by_field_of_dec_dev) = 9,135
Same data, random sorts, gives these similarity values:
Random similarity(0) = 55
Random similarity(1) = 61
Random similarity(2) = 54
Random similarity(3) = 60
Random similarity(4) = 68
Random similarity(5) = 55
Random similarity(6) = 56
Random similarity(7) = 58
Random similarity(8) = 56
Random similarity(9) = 63
一个相当不错的近似（模拟退火方式）解：
从项目的任意（或随机）排列开始。可选：选择 N 个随机排列（比如 10 或 100）并从总误差最低的排列开始，丢弃其他排列。
选择两个不同的随机索引并交换这些索引处的项目，如果它会减少总误差（你可以通过计算“之前”和“之后”列表的总误差来直接做到这一点，但是您也可以通过交换和不交换来检查项目 i-1, i, i+1 和 j-1, j, j+1；所有其他导致错误的因素保持不变。
重复上一步，直到您选择某个停止条件，可以是以下一个或多个：
- 您达到了一些预定义的迭代次数或执行时间限制，
- 总误差低于某个阈值，
- 过去 N 次迭代中“成功交换”的百分比低于阈值，
- 您进行了 N 次迭代而没有成功交换。
这改进了我之前的答案，并且还表明按列排序的列顺序是通过增加该列中数字的 std-deviations 确实 给出更好的结果结果。
一个额外的算法采用最佳排序并交换相邻行（如果这增加了整体相似性）直到没有更多的相邻交换改进结果。
代码
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 17 07:30:23 2022
@author: paddy
"""
import random
from itertools import permutations
from typing import List, Tuple
DType = List[Tuple[int, int, int]]
def randomised_data_gen(n: int) -> DType:
def f(n):
return random.randint(0, n)
return [(f(n // 30), f(n // 20), f(n // 10)) for _ in range(n)]
def stddev_mean(lst: List[int]) -> Tuple[float, float]:
"Standard deviation of numbers in lst, mean."
sm = sum(lst)
sm2 = sum(i**2 for i in lst)
n = len(lst)
return ((sm2 - sm**2 / n) / n)**0.5, sm / n
def similarity(d: DType) -> int:
"Compare successive 3-tuples for similarity - higher is better"
return sum(sum((col0 == col1) for col0, col1 in zip(d0, d1)) for d0, d1 in zip(d, d[1:]))
def sort_by_column(data: DType, column_index: Tuple[int]) -> DType:
return sorted(data, key=lambda d: [d[i] for i in column_index])
def similarity_when_randomized(data: DType, n: int = 10) -> None:
dcopy = data.copy()
sims = ", ".join([f"{similarity(dcopy):_}", random.shuffle(dcopy)][0] for _ in range(n))
print(f" Same data random sorts gives similarity values: {sims}")
#%% Test data
def test1():
data = [ # SIMILARITY in columns of sucessive records
(0, 1, 2),
(2, 4, 2), # 1
(3, 2, 1), # 0
(4, 3, 4), # 0
(3, 3, 1), # 1
(1, 2, 2), # 0
(4, 0, 3), # 0
(0, 3, 5), # 0
(1, 5, 1), # 0
(1, 5, 2), # 2
] # Sum = 4
assert similarity(data) == 4
test1()
#%% Randomised data
print("NOTE: Similarity figures are better when higher.\n")
n = 10_000
data = randomised_data_gen(n)
print(f"Random generation of {n} items has similarity of = {similarity(data)}")
similarity_when_randomized(data, 10)
col_stddev = [(i, stddev_mean([datum[i] for datum in data])[0]) for i in range(len(data[0]))]
print(f"\n(Column_index, Standard_deviation) of each column of numbers: {col_stddev}")
#%% Order by increasing stddeviation column
index_by_inc_dev = [ind for ind, _ in sorted(col_stddev, key=lambda x: x[1])]
#%% Sort by columns
def score_all_column_orders(data: DType) -> Tuple[List[Tuple[int, Tuple[int, int, int]]], DType]:
"Print and return similarity scores for sorting data by all column orders, best first AND the best sort of data"
sim_by_column_sort = [(similarity(sort_by_column(data, column_order)), column_order)
for column_order in permutations(range(len(data[0])))]
sim_by_column_sort.sort(reverse=True) # Highest similarity first
print("\nSimilarity when sorting by all column orders:")
print(" SIMILARITY SORT_COLUMN_ORDER")
for sim, col in sim_by_column_sort:
col = list(col)
if col == index_by_inc_dev[::-1]:
comment = " (by DEcreasing std-dev)"
elif col == index_by_inc_dev:
comment = " (by INcreasing std-dev)"
else:
comment = ""
print(f" {sim:>10_} {col}{comment}")
return sim_by_column_sort, sort_by_column(data, sim_by_column_sort[0][1])
_, best_by_col_sort = score_all_column_orders(data)
score = best_score = similarity(best_by_col_sort)
#%% Swap with next row
print("\nNeighbourly swaps:")
twizzled = best_by_col_sort.copy()
while True:
swaps = 0
for i in range(1, len(twizzled) - 2):
#breakpoint()
i_window = [ twizzled[x] for x in [i-1, i, i+1, i+2]]
i_swap = [ twizzled[x] for x in [i-1, i+1, i, i+2]]
if similarity(i_swap) > similarity(i_window):
twizzled[i], twizzled[i+1] = twizzled[i+1], twizzled[i]
swaps += 1
if swaps == 0:
break
print(f" Neighbour {swaps = } New similarity = {similarity(twizzled)}")
示例输出
NOTE: Similarity figures are better when higher.
Random generation of 10000 items has similarity of = 70
Same data random sorts gives similarity values: 70, 57, 65, 57, 51, 61, 64, 56, 63, 50
(Column_index, Standard_deviation) of each column of numbers: [(0, 96.5443987139596), (1, 145.326873357098), (2, 288.69842362782305)]
Similarity when sorting by all column orders:
SIMILARITY SORT_COLUMN_ORDER
9_978 [0, 1, 2] (by INcreasing std-dev)
9_829 [0, 2, 1]
9_802 [1, 0, 2]
9_638 [1, 2, 0]
9_160 [2, 0, 1]
9_142 [2, 1, 0] (by DEcreasing std-dev)
Neighbourly swaps:
Neighbour swaps = 12 New similarity = 9990
采用随机组合优化算法，如tabu search, a genetic algorithm, or simulated annealing。根据我的经验，我已经订购了降低效率的替代品。
所有这些都涉及从一个或多个随机解决方案开始，然后通过随机扰动和一种决定保留哪些解决方案的方法在连续迭代中改进结果。 objective 函数（在您的情况下是完全不同）会指导您进行改进。对于您提到的数字，几千次迭代后您将获得接近最优的解决方案。
也许这可以帮到你。这是一种你必须验证的方法，我没有时间开发它，但我认为它是可行的。
如果元素列表是有序的，它的排序将是微不足道的：线性的。将每个元素与下一个元素进行比较就足够了。
如果只有一些元素放错了位置但接近它们的正确位置，排序会稍微慢一些，但也很快。大多数时候，每个元素都会与下一个元素进行比较，有些元素需要进行一些额外的比较才能放置到位。
基于以上，我的做法是轻松得到一个比较有序的列表。为此，根据元素的线性回归进行排序就足够了（如果我没记错的话）。我将在二维中解释它（元素具有 2 个值而不是 3 个），因为它更简单，但将它传递到 3 个维度，正如你在问题中所问的，并不复杂。
您对所有元素进行初始 运行 并计算回归线。 然后，计算回归线变为 Y=0 所需的旋转并将该旋转应用于您的点。这允许您 运行 按顺序从左到右遍历点。该顺序就是您用作第一个排序顺序的顺序。
显然，两个相邻的点可能不是彼此最接近的，但很少会有更接近的点，因此最终排序将始终是局部的并且需要很少的移动。
也就是说，我们使用回归线作为元素应该具有的最终位置的近似值。很明显，在回归线上相距较远的两个元素（运行ning 从一端到另一端）也相距较远，这使我们能够以接近最佳的方式排列它们。
这迫使我们进行几次计算，这些计算不是很复杂，但比每对元素之间的比较复杂得多。也就是说，比较少的情况下，这种方法的成本更高，但在某一点上，这种方法比在元素之间进行大量比较要好。
要将其移动到 3 维（并使用您需要的 3 个分量），您必须使用 3D 回归线并获得 3 维旋转矩阵。其他类似。
drop-in 替代 Andrej Kesely 的方法，在同一测试中速度提高了大约 30 倍。该方法通过始终在输出中附加与最后一个最相似的剩余三元组来构建输出列表。大多数时候，剩下的三元组至少在一个位置上与最后一个匹配。因此，我没有检查 all 剩余的三元组的相似性，而是首先只检查在至少一个位置匹配的剩余三元组。只有当失败时，我才会检查所有剩余的三元组。我使用索引并打破与它们的相似关系，所以我得到与 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
如果我用这个替换 for mark in enumerate(out[-1]) 循环，它会快大约 35 倍，这不会比较我已经知道的匹配点：
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