相关疑难解决方法(0)

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

该套装很小(10至30件),因此性能并不重要.

每种类型的物品数量或类型数量没有限制,数据可以被认为是随机的.

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

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

我想产生类似: A,B,C,A,D,F,B,A,E,C,A,D,B,A

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

是否有算法来实现这一目标？

-Update-

在交换了一些评论后,我得出了一个次要目标的定义:

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

- 更新2-

关于答案.有很多有用的答案,虽然没有一个是两个目标的解决方案,特别是第二个是棘手的.

关于答案的一些想法:

• PengOne:听起来很不错,虽然它没有提供具体的实现,但并不总能根据第二个目标获得最佳结果.
• Evgeny Kluev:为主要目标提供具体实施,但根据次要目标不会产生最佳结果.
• tobias_k:我喜欢随机方法,它并不总能带来最好的结果,但它是一个很好的近似和成本效益.

我试过叶夫根Kluev,回溯,和tobias_k式的组合,但它需要太多的时间来得到结果.

最后,至少对于我的问题,我认为tobias_k是最合适的算法,因为它的简单性和及时的良好结果.可能使用模拟退火可以改善它.