用于分隔相同types的项目的algorithm

我有一个元素列表,每个元素用一个types标识,我需要重新sorting列表,以最大化相同types的元素之间的最小距离

这个集合很小(10到30个),所以performance并不重要。

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

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

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

我想产生像这样的: ABCADFBAECADBA

  • 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:

  1. A至less4分开,B至less4分开,C至less2分开
  2. A至less3分开,B至less3分开,C至less4分开

你需要一个明确的“好”的措施(或者更准确地说,“更好”)。 我现在假设的措施是: 最大化任何两个相同的项目之间的最小距离

这里有一个algorithm实现了最小ceiling(N/n(A))距离ceiling(N/n(A)) ,其中N是项目总数, n(A)是实例A的项目数量,假设A是最多的。

  • 订购项目typesA1, A2, ... , Ak ,其中n(Ai) >= n(A{i+1})
  • 初始化列表L为空。
  • 对于从k1 j ,尽可能在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值,然后再把这些物品排列出来解决这个问题。