我有一个元素列表，每个元素都用一种类型标识，我需要对列表进行重新排序，以 使 相同类型的元素之间的 最小距离 最大化 。
套装很小（10至30件），因此性能并不是很重要。
每种类型的项目数量或类型的数量没有限制，可以认为数据是随机的。
例如，如果我有以下列表：
我想产生类似： A，B，C，A，D，F，B，A，E，C，A，D，B，A
A
B
C
D
F
E
是否有实现此目的的算法？
-更新-
在交换了一些意见之后，我得出了第二个目标的定义：
-更新2-
关于答案。有很多有用的答案，尽管没有一个解决方案可以同时实现这两个目标，特别是第二个棘手的问题。
关于答案的一些想法：
我尝试将Evgeny Kluev，回溯和tobias_k公式结合起来使用，但要花费太多时间才能得到结果。
最后，至少对于我的问题，我认为tobias_k是最合适的算法，因为它的简单性和及时的良好结果。可能可以使用 模拟退火 进行改进。
这听起来像是一个有趣的问题，所以我尝试了一下。这是我用Python完成的超级简单的随机方法：
def optimize(items, quality_function, stop=1000): no_improvement = 0 best = 0 while no_improvement < stop: i = random.randint(0, len(items)-1) j = random.randint(0, len(items)-1) copy = items[::] copy[i], copy[j] = copy[j], copy[i] q = quality_function(copy) if q > best: items, best = copy, q no_improvement = 0 else: no_improvement += 1 return items
正如评论中已经讨论的那样，真正棘手的部分是质量函数，将其作为参数传递给优化器。经过一番尝试，我想出了一个几乎总是可以产生最佳结果的方法。感谢 pmoleri ，指出了如何提高整体效率。
def quality_maxmindist(items): s = 0 for item in set(items): indcs = [i for i in range(len(items)) if items[i] == item] if len(indcs) > 1: s += sum(1./(indcs[i+1] - indcs[i]) for i in range(len(indcs)-1)) return 1./s
这是一些随机结果：
>>> print optimize(items, quality_maxmindist) ['A', 'B', 'C', 'A', 'D', 'E', 'A', 'B', 'F', 'C', 'A', 'D', 'B', 'A']
请注意，通过另一个质量函数，可以将同一优化器用于不同的列表重排任务，例如作为（而不是愚蠢的）随机排序器。
