Geek Answers Handbook

Sort the list so that the gap between equal elements is as large as possible

Suppose I have unsorted List, containing a, a, b, b, a, c, and I want this sequence to be sorted so that the gaps between equal elements are as possible. Therefore, in the case of this sequence of samples, a possible yield may be b, a, c, a, b, a. In my application, it would not be so important that the gaps are at its exact average maximum, but there should not be two equal elements next to each other, when possible. So my digression is to maximize the smallest spaces.

+4
source share
2 answers

I would start by measuring the frequency for each unique element:

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))

So now you can create a more or less scattered list:

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)

Each subsequent iteration here is based on the previous one with a higher frequency: elements that are simply inserted into the list (from the previous iteration) are as wide as possible. Thus, this may not be as effective if the frequency is significantly reduced between iterations, since too frequent elements cannot be “too twisted”.

This algorithm does not try to maximize each distance - it tries to reduce the likelihood of grouped elements to a minimum. Just a random shuffle should do the similar thing if you are okay with a less accurate result, since it creates groups with a still small, but slightly higher probability:

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

, , . , list.size, :

def maxGaps[A](in: List[A]): List[A] = {
  if (in.isEmpty) return in

  def noPairs(xs: List[A]): Boolean =
    xs.sliding(2, 1).forall { case List(a, b) => a != b }

  val (good, bad) = in.permutations.partition(noPairs)
  val candidates = if (good.nonEmpty) good else bad

  val maxDist = in.size

  def calcScore(xs: List[A], accum: Int = 0): Int =
    xs match {
      case head :: tail =>
        val i = tail.indexOf(head)
        val j = if (i < 0) maxDist else i
        calcScore(tail, accum + j)      
      case Nil => accum
    }

  candidates.maxBy(calcScore(_))
}

maxGaps("aabbac".toList) // abacab
+1

More articles:


All Articles