我有一个(可能很大的)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])"尽可能相似".
将两个三元组的相似性定义为它们之间不相等的元素数.E、 g.
-
(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.
Question:找到data的排序的好算法是什么，它可以最小化所有相邻三元组之间的差异之和？
一些代码
下面是一个计算两个三元组之间差异的函数:
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个).就我而言，这些都是等价的，我只想要其中一个.
最后的 comments
实际上，data的大小可能与10000一样大.
广受追捧的算法应该比O(N！)，i、 e.在时间(和空间)上可能是多项式.
如果不存在这样的算法，我会对"近似解"感兴趣，即一种快速算法，它给出data的排序，总分数很小，但不一定最小.其中一种算法是lexicographic sorting，即.
sorted(data) # score 18
虽然我希望能做得更好.
编辑(对已接受解决方案的 comments )
我已经try 过以下作为代码给出的所有启发式解决方案(我没有try 过谷歌或工具).对于大len(data)，我发现Andrej Kesely的解决方案既快又能给出最好的结果.
这种方法背后的 idea 很简单.数据元素(3元组)的排序列表将逐个建立.给定某个数据元素，下一个元素将被 Select 为剩余(尚未排序)数据中最相似的元素.
从本质上讲，这解决了问题的本地化版本，即我们只"向前看"，而不是在整个数据集上进行全局优化.我们可以想象一个面向future n种算法的层次 struct ，每种算法都能连续提供更好(或至少同样好)的结果，但代价是成本要高得多.安德烈·凯斯利(Andrej Kesely)的解决方案在这个层次 struct 中处于最低位置.位于最高点的算法向前看len(data)，准确地解决了问题.
让我们满足于"展望future "，即Andrej Kesely的答案.这就为a)初始元素的 Select ，b)当几个元素都是下一个元素使用的最佳候选元素(相同的差异性)时该怎么做留下了空间. Select data中的第一个元素作为初始元素，以及具有最小差异的元素的第一次出现，a)和b)都是根据data中元素的原始顺序确定的.正如Andrej Kesely指出的，提前(lex)对data进行排序会有所帮助.
最后，我采用了这个解决方案，但在以下几个方面进行了改进:
- 我try 了6个
data的初始排序算法；列(0, 1, 2)、(2, 0, 1)、(1, 2, 0)的lex排序，所有列都按升序和降序排列. - 对于大
len(data)，算法对我来说太慢了.我怀疑它的规模像O(n²).因此，我独立处理大小为n_max的数据块，最终结果是将不同的排序块连接起来.从一个块过渡到下一个块时，我们希望差异为3，但如果我们保持n_max大，这并不重要.我和n_max = 1000一起go .
作为实现说明，不使用data.pop(idx)可以提高性能，因为data.pop(idx)本身就是O(n).用另一个标记代替原来使用的数据 struct ，或者用另一个标记代替原来使用的数据 struct .