Сглаживание списка [List [Int]] при сохранении только выбранных членов - PullRequest
Новая
       13

Сглаживание списка [List [Int]] при сохранении только выбранных членов

1 голос
/ 27 февраля 2012

Существует список [List [Int]] простых факторов для целых чисел 2..12: 

List(List(2), List(3), List(2, 2), List(5), List(3, 2), 
     List(7), List(2, 2, 2), List(3, 3), List(5, 2), 
     List(11), List(3, 2, 2))

Он должен быть сведен так, чтобы результирующая структура данных содержала только самую длинную последовательность (наибольшую мощность) каждого простого числа: 

List(2,2,2,3,3,5,7,11)

Например, исключая все, кроме величайшей силы двух:
Список (Список ( 2 ), Список (3), Список ( 2, 2 ), Список (5), Список (3 , 2 ), Список (7), Список ( 2, 2, 2 ), Список (3, 3), Список (5 , 2 ), Список (11), Список (3 , 2, 2 ))

В исходном списке подсписки простых чисел всегда сортируются в порядке убывания.

Пытается найти элегантное, предпочтительно ≤O (n) решение.

Мое решение далеко от идеального: 

xs.flatMap(l=> l.groupBy(x=>x)).map(x=>(x._1,x._2.length)).
   groupBy(_._1).mapValues(_.maxBy(_._2)).values.
   map(x=>List.fill(x._2) (x._1)).flatten

Ответы [ 3 ]

1 голос
/ 27 февраля 2012

Это немного короче, чем у вас; концептуально это достаточно близко, так что я думаю, что вы можете понять это: 

xs.flatMap(_.groupBy(x=>x)).groupBy(_._1).
  flatMap(_._2.sortBy(- _._2.length).head._2).toSeq.sorted
1 голос
/ 28 февраля 2012

После некоторого анализа проблема сводится к простому объединению двух отсортированных списков, но с небольшим поворотом - дублирующие элементы должны добавляться только один раз: 

merge(List(5,3,3,2),List(7,5,3,2,2)

Должны произвести: 

List(7,5,3,3,2,2)

Когда есть такая замечательная функция merge, список списков можно просто уменьшить слева направо.

Решение 

def merge (xs:List[Int],ys:List[Int]):List[Int] = (xs,ys) match{
  case (Nil,_)         => ys
  case (_,Nil)         => xs
  case (x::xxs,y::yys) => if (x==y) x::merge(xxs,yys) 
                          else if (x>y) x::merge(xxs,ys) 
                          else y::merge(xs,yys)
}

// note the simplicity of application
ll reduce merge

Хвостовая рекурсивная версия merge - предотвращение переполнения стека в длинных списках: 

def merge (xs:List[Int],ys:List[Int]) = {
  def m (rs:List[Int],xs:List[Int],ys:List[Int]):List[Int] = (xs,ys) match {
    case (Nil,_)         => ys reverse_:::rs
    case (_,Nil)         => xs reverse_:::rs
    case (x::xxs,y::yys) => if (x==y) m(x::rs,xxs,yys) 
                            else if (x>y) m(x::rs,xxs,ys) 
                            else m(y::rs,xs,yys)
  }

  m(Nil,xs,ys).reverse   
}

Более быстрая императивная версия merge: 

def merge (x:List[Int],y:List[Int]) = {
  var rs = new scala.collection.mutable.ListBuffer[Int]()
  var xs = x
  var ys = y
  while(!xs.isEmpty && !ys.isEmpty) {
    if (xs.head>ys.head) {
      rs+=xs.head
      xs=xs.tail
    } else if(xs.head==ys.head) {
      rs+=xs.head
      xs=xs.tail
      ys=ys.tail
    } else {
      rs+=ys.head
      ys=ys.tail          
    }
  }
  rs ++= xs ++= ys toList
}
0 голосов
/ 27 февраля 2012 
val ll = List(List(2), List(3), List(2, 2), List(5), List(3, 2),  
     List(7), List(2, 2, 2), List(3, 3), List(5, 2), 
     List(11), List(3, 2, 2))
val s = ll.flatten toSet 
s.map (n => ll.map (l => (n, l.count (_ == n)))).map (l => (l(0) /: l.tail) ((a, b) => if (a._2 > b._2) a else b))

производит: 

scala.collection.immutable.Set[(Int, Int)] = Set((7,1), (11,1), (2,3), (5,1), (3,2))

, расширяя факторы и сортируя их, чтобы сформировать List (2,2,2,3,3,5,7,11), оставленный в качестве упражнения

...