用于分隔相同types的项目的algorithm
我有一个元素列表，每个元素用一个types标识，我需要重新sorting列表，以最大化相同types的元素之间的最小距离 。
这个集合很小（10到30个），所以performance并不重要。
每种types的物品的数量或types的数量没有限制，数据可以被认为是随机的。
例如，如果我有一个列表：
- A的5项
- B的3项
- C项2项
- D项2项
- E的1项
- F的1项
我想产生像这样的： A ， B ， C ， A ， D ， F ， B ， A ， E ， C ， A ， D ， B ， A
- A之间至less有2个项目
- B有至less4项之间的事件
- C有6个项目发生之间
- D有6个项目发生之间
有没有一个algorithm来实现这个？
-Update-
在交换了一些意见之后，我提出了一个次要目标的定义：
- 主要目标 ：最大化相同types元素之间的最小距离，只考虑距离较小的types。
- 次要目标 ：最大化每种types的元素之间的最小距离。 IE：如果一个组合增加了某种types的最小距离而不减less其他的，那就select它。
更新2-
关于答案。 有很多有用的答案，虽然没有一个是解决这两个目标，特别是第二个是棘手的。
关于答案的一些想法：
- PengOne ：听起来不错，虽然没有提供具体的实施，并不总是按照第二个目标达到最好的结果。
- Evgeny Kluev ：为主要目标提供了具体的实施，但根据次要目标并没有达到最佳结果。
- tobias_k：我喜欢随机的方法，它并不总是会导致最好的结果，但它是一个很好的近似和成本效益。
我尝试了Evgeny Kluev，backtracking和tobias_k公式的组合，但是需要太多的时间来获得结果。
最后，至less对于我的问题，我认为tobias_k是最适合的algorithm，因为它的简单性和及时的好结果。 可能使用模拟退火可以改进。
这听起来像一个有趣的问题，所以我只是试了一下。 这是我用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
正如在评论中已经讨论的那样，真正棘手的部分是质量函数，作为parameter passing给优化器。 经过一番尝试，我想出了一个几乎总是产生最佳结果的产品。 感谢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']
请注意，传递另一个质量函数，相同的优化器可以用于不同的列表重新排列任务，例如作为（非常愚蠢的）随机分拣机。
首先，你还没有一个明确的优化问题。 如果你想最大化两个相同types的项目之间的最小距离，这是很好的定义。 如果你想最大化两个A之间的距离和两个B之间和两个Z之间的最小距离，那么这个问题就没有明确的定义。 你会如何比较两个解决scheme：
- A至less4分开，B至less4分开，C至less2分开
- A至less3分开，B至less3分开，C至less4分开
你需要一个明确的“好”的措施（或者更准确地说，“更好”）。 我现在假设的措施是： 最大化任何两个相同的项目之间的最小距离 。
这里有一个algorithm实现了最小ceiling(N/n(A))距离ceiling(N/n(A)) ，其中N是项目总数， n(A)是实例A的项目数量，假设A是最多的。
- 订购项目types
A1, A2, ... , Ak，其中n(Ai) >= n(A{i+1})。 - 初始化列表
L为空。 - 对于从
k到1j，尽可能在L分配types为a的项目。
示例：给定问题中的分布，该algorithm产生：
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
这是一个algorithm，只是最大化相同types的元素之间的最小距离，除此之外什么都不做。 以下列表用作示例：
AAAAA BBBBB CCCC DDDD EEEE FFF GG
- 按照每个types的元素数量以降序排列元素集合。 实际上，只有最大集合（A＆B）应该放在列表的头部，以及那些只有一个元素（C＆D＆E）的元素集合。 其他集可能未sorting。
- 在arrays中为每个最大集合中的一个元素保留R的最后位置，将剩余的arrays平均分配到最大集合的S-1个剩余元素之间。 这给出了最佳距离：K =（N-R）/（S-1）。 将目标arrays表示为具有K列和L = N / K全行的二维matrix（并且可能有一个具有N％K个元素的部分行）。 例如，我们有R = 2，S = 5，N = 27，K = 6，L = 4。
- 如果matrix有S – 1个满行，填充matrix的前R列与最大集（A＆B）的元素，否则顺序填充所有列，从最后一列开始。
对于我们的例子，这给出：
AB.... AB.... AB.... AB.... AB.
如果我们试图用相同的顺序填充其他列，那么就有一个问题：
ABCDE. ABCDE. ABCDE. ABCE.. ABD
最后的'E'只有第一个'E'的5个位置。
- 按顺序填充所有列，从最后一列开始。
对于我们的例子，这给出：
ABFEDC ABFEDC ABFEDC ABGEDC ABG
回到线性arrays，我们有：
ABFEDCABFEDCABFEDCABGEDCABG
这里试图对这个问题使用模拟退火（C源代码）： http : //ideone.com/OGkkc 。
我相信你可以看到你的问题就像一堆物理排斥海誓山盟的粒子。 你可以迭代到一个“稳定”的情况。
基本的伪代码：
force( x, y ) = 0 if x.type==y.type 1/distance(x,y) otherwise nextposition( x, force ) = coined?(x) => same else => x + force notconverged(row,newrow) = // simplistically row!=newrow row=[a,b,a,b,b,b,a,e]; newrow=nextposition(row); while( notconverged(row,newrow) ) newrow=nextposition(row);
我不知道它是否收敛，但这是一个想法:)
我相信可能有一个更有效的解决scheme，但这是你的一个可能性：
首先，请注意，find一个产生最小相距为1的项之间的距离的sorting是很容易的。只要使用任何随机sorting，MDBIOST将至less为1，如果不是更多的话。
因此，首先假定MDBIOST为2. 根据MDBIOST为2的假设，对可能的sorting空间进行recursionsearch。 您可以使用多种条件从此search中剪除分支。 如果您发现有效的订购，请终止search。
如果你发现一个工作，再试一次，假设MDBIOST将是3.然后4 …等等，直到search失败。
更新：从高数开始实际上会更好，因为这将更多地限制可能的select。 然后逐渐减less数量，直到你find一个有效的顺序。
这是另一种方法。
如果每个项目必须至less与其他同types的项目保持k个地点，则从左到右记下项目，跟踪每个项目剩下的项目数量。 在每个点放下一个剩下最多的物品，你可以合法地放下。
如果没有超过相同types的细胞（N / k）物品，这将适用于N个物品，因为它将保存这个物品 – 在放下k个物品之后，我们减less了k个物品，并且放下至less一个每种types都以该types的ceil（N / k）项目开始。
给出一个混合物品的混合物，你可以计算出你能支持的最大的k值，然后再把这些物品排列出来解决这个问题。
