- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我有一个元素列表,每个元素都有一个类型,我需要重新排序列表以最大化相同类型元素之间的最小距离。
该集合很小(10 到 30 个项目),因此性能并不是很重要。
对于每种类型的项目数量或类型数量没有限制,数据可以认为是随机的。
例如,如果我有一个列表:
我想制作这样的东西:A
, B
, C
, A
, D
, F
, B
, A
, E
, C
, A
, D
, B
, A
有算法可以实现吗?
-更新-
在交换了一些意见之后,我得出了次要目标的定义:
-更新 2-
关于答案。有很多有用的答案,尽管没有一个解决方案可以同时满足两个目标,尤其是第二个目标,这很棘手。
关于答案的一些想法:
我尝试了 Evgeny Kluev、回溯和 tobias_k 公式的组合,但它需要太多时间才能得到结果。
最后,至少对于我的问题,我认为 tobias_k 是最合适的算法,因为它简单且及时获得良好结果。可能可以使用模拟退火对其进行改进。
最佳答案
首先,您还没有明确定义的优化问题。如果您想最大化相同类型的两个项目之间的最小距离,那是明确定义的。如果你想最大化两个 A 之间和两个 B 之间以及......以及两个 Z 之间的最小距离,那么这并没有明确定义。您如何比较两种解决方案:
您需要明确定义“好”(或者更准确地说,“更好”)的衡量标准。我现在假设该措施是:最大化同一项目中任意两个项目之间的最小距离。
这是一个实现最小距离 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
关于分离相同类型项目的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12375831/
现在我正在尝试实现 flash programming specification对于 PIC32MX。我正在使用 PIC32MX512L 和 PIC32MX512H。 PIC32MX512L最终必须
我是一名优秀的程序员,十分优秀!