algorithm - 排序列表，使相等元素之间的差距尽可能大

Question

假设我有一个未排序的 List包含 a, a, b, b, a, c 并且我希望对这个序列进行排序，以便相等元素之间的间隙尽可能大。因此，对于此示例序列，可能的输出可能是 b, a, c, a, b, a。在我的应用程序中，间隙是否处于其精确的平均最大值并不那么重要，但只要有可能，两个相等的元素就不应该相邻。所以我的缩进是最大化最小的差距。

Answer 1

我将从测量每个独特元素的频率开始:

scala> val l = List("a", "a", "b", "b", "a", "c")
l: List[String] = List(a, a, b, b, a, c)

scala> val in = l.toSet[String].map(x => x -> l.count(x==)).toList.sortBy(_._2).reverse
in: List[(String, Int)] = List((a,3), (b,2), (c,1))

所以现在你可以生成更多更少的分散列表:

def shuffle[T](l: List[T]) = {

   def fill(n: Int, l: List[List[T]], s: T) = 
      l.take(n + 1).reduce(_ ++ List(s) ++ _) ++ l.drop(n + 1).flatten

   val in = l.toSet[T].map(x => x -> l.count(x==)).toList.sortBy(_._2).reverse

   val initial = in.head._2 -> List.fill(in.head._2)(in.head._1)

   in.tail.foldLeft(initial){case ((size, acc), (value, count)) => 
     count -> fill(count, acc.grouped(acc.size / size).toList, value)
   }._2
}

scala> shuffle(l)
res32: List[String] = List(a, b, c, a, b, a)

此处的每个下一次迭代都基于前一个频率更高的迭代:元素刚刚插入到列表中(来自上一次迭代)尽可能广泛。因此，如果频率在迭代之间显着下降，则它可能不会那么有效，因为高频元素可能没有被充分“扰乱”。

该算法并不是试图最大化每个距离 - 它试图将分组元素出现的概率降至最低。如果你对不太精确的结果没问题，那么随机洗牌应该做类似的事情，因为它产生的组仍然很小但这里的概率更高:

scala> scala.util.Random.shuffle(l)
res34: List[String] = List(a, b, c, b, a, a)