分离相同类型项目的算法

Question

我有一个元素列表，每个元素都有一个类型，我需要重新排序列表以最大化相同类型元素之间的最小距离。

该集合很小(10 到 30 个项目)，因此性能并不是很重要。

对于每种类型的项目数量或类型数量没有限制，数据可以认为是随机的。

例如，如果我有一个列表:

• 5 项 A
• B 3 项
• 2项C
• D 2 项
• 1 项 E
• F 的 1 项

我想制作这样的东西: A, B, C, A, D, F, B, A, E, C, A, D, B, A

• A 在两次出现之间至少有 2 个项目
• B 在两次出现之间至少有 4 个项目
• C 在两次出现之间有 6 个项目
• D 在两次出现之间有 6 个项目

有算法可以实现吗？

-更新-

在交换了一些意见之后，我得出了次要目标的定义:

• 主要目标:最大化相同类型元素之间的最小距离，只考虑距离较小的类型。
• 次要目标:每种 类型的元素之间的最小距离最大化。 IE:如果一个组合增加了某种类型的最小距离而不减少其他类型，则选择它。

-更新 2-

关于答案。 有很多有用的答案，尽管没有一个解决方案可以同时满足两个目标，尤其是第二个目标，这很棘手。

关于答案的一些想法:

• PengOne:听起来不错，虽然它没有提供具体的实现，并且根据第二个目标并不总是导致最好的结果。
• Evgeny Kluev:提供了主要目标的具体实现，但并没有根据次要目标带来最佳结果。
• tobias_k:我喜欢随机方法，它并不总能带来最佳结果，但它是一个很好的近似值并且具有成本效益。

我尝试了 Evgeny Kluev、回溯和 tobias_k 公式的组合，但它需要太多时间才能得到结果。

最后，至少对于我的问题，我认为 tobias_k 是最合适的算法，因为它简单且及时获得良好结果。可能可以使用模拟退火对其进行改进。

Answer 1

首先，您还没有明确定义的优化问题。如果您想最大化相同类型的两个项目之间的最小距离，那是明确定义的。如果你想最大化两个 A 之间和两个 B 之间以及......以及两个 Z 之间的最小距离，那么这并没有明确定义。您如何比较两种解决方案:

1. A 至少相隔 4 个，B 至少相隔 4 个，C 至少相隔 2 个
2. A 至少相隔 3 个，B 至少相隔 3 个，C 至少相隔 4 个

您需要明确定义“好”(或者更准确地说，“更好”)的衡量标准。我现在假设该措施是:最大化同一项目中任意两个项目之间的最小距离。

这是一个实现最小距离 ceiling(N/n(A)) 的算法，其中 N 是项目总数，n(A ) 是实例 A 的项数，假设 A 是最多的。

• 订购项目类型 A1, A2, ... , Ak 其中 n(Ai) >= n(A{i+1})。
• 将列表 L 初始化为空。
• 对于从k到1的j，在中尽可能均匀地分布Ak类型的项目>L.

示例:给定问题中的分布，算法产生:

F
E, F
D, E, D, F
D, C, E, D, C, F
B, D, C, E, B, D, C, F, B
A, B, D, A, C, E, A, B, D, A, C, F, A, B