Subject: Overcoming type-2 [WebMD]

From: Doc.Peirson <[email-masked]>
Date: Tue, 06 Jan 2015 08:13:09 -0800

American Diabetes Center

Warning: This infomation saves thousads of lives every time it's shown.

The truth about type-2 and what it means to "reverse" it.

www.abc/the-truth-about-type-2/60 minutes-release.html

Posted: Jan 06 2015

The contents of this e-mail message and any attachments are confidential and are intended solely for addressee. Washington WWS Associates | 3901 Tyler St | Mineappolis | MN [your-mail/settings] We are operated under the control of the national-DBS source

Lets assume we have a Scala list:

val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1)

We can easily remove duplicates using the following code:

l1.distinct

or

l1.toSet.toList

But what if we want to remove duplicates only if there are more than 2 of them? So if there are more than 2 elements with the same value we remain only two and remove the rest of them.

I could achieve it with following code:

l1.groupBy(identity).mapValues(_.take(2)).values.toList.flatten

that gave me the result:

List(2, 2, 5, 1, 1, 3, 3)

Elements are removed but the order of remaining elements is different from how these elements appeared in the initial list. How to do this operation and remain the order from original list?

So the result for l1 should be:

List(1, 2, 3, 1, 3, 2, 5)

scala

share|improve this question

edited Dec 22 '14 at 21:23

Jacek Laskowski

8,80831952

asked Dec 12 '14 at 23:04

rtruszk

2,15411333

Do you prefer folding or recursion? If you keep the state of the already seen fields with their number, you just need to filter out those values that already occurred too often. Gbor Bakos Dec 12 '14 at 23:23

I do not prefer folding or recursion. If there are many different answers I want to see them
. rtruszk Dec 12 '14 at 23:27

add a comment

12 Answers

activeoldestvotes

up vote

9

down vote

accepted

Not the most efficient.

scala> val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1)

l1: List[Int] = List(1, 2, 3, 1, 1, 3, 2, 5, 1)

scala> l1.zipWithIndex.groupBy( _._1 ).map(_._2.take(2)).flatten.toList.sortBy(_._2).unzip._1

res10: List[Int] = List(1, 2, 3, 1, 3, 2, 5)

share|improve this answer

edited Dec 24 '14 at 7:16

dk14

3,404519

answered Dec 13 '14 at 0:31

Soumya Simanta

3,29923669

add a comment

up vote

6

down vote

My humble answer:

def distinctOrder[A](x:List[A]):List[A] = {

@scala.annotation.tailrec

def distinctOrderRec(list: List[A], covered: List[A]): List[A] = {

(list, covered) match {

case (Nil, _) => covered.reverse

case (lst, c) if c.count(_ == lst.head) >= 2 => distinctOrderRec(list.tail, covered)

case _ => distinctOrderRec(list.tail, list.head :: covered)

}

}

distinctOrderRec(x, Nil)

}

With the results:

scala> val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1)

l1: List[Int] = List(1, 2, 3, 1, 1, 3, 2, 5, 1)

scala> distinctOrder(l1)

res1: List[Int] = List(1, 2, 3, 1, 3, 2, 5)

On Edit: Right before I went to bed I came up with this!

l1.foldLeft(List[Int]())((total, next) => if (total.count(_ == next) >= 2) total else total :+ next)

With an answer of:

res9: List[Int] = List(1, 2, 3, 1, 3, 2, 5)

share|improve this answer

edited Dec 13 '14 at 7:04

answered Dec 13 '14 at 1:34

Daniel Hinojosa

41225

add a comment

up vote

5

down vote

Not the prettiest. I look forward to seeing the other solutions.

def noMoreThan(xs: List[Int], max: Int) =

{

def op(m: Map[Int, Int], a: Int) = {

m updated (a, m(a) + 1)

}

xs.scanLeft( Map[Int,Int]().withDefaultValue(0) ) (op).tail

.zip(xs)

.filter{ case (m
, a) => m(a) <= max }

.map(_._2)

}

scala> noMoreThan(l1, 2)

res0: List[Int] = List(1, 2, 3, 1, 3, 2, 5)

share|improve this answer

edited Dec 12 '14 at 23:59

answered Dec 12 '14 at 23:50

experquisite

35419

I am glad we provided different angles. :) (I have borrowed your max parameter. Hope you do not mind.) Gbor Bakos Dec 12 '14 at 23:54

I added your withDefaultValue. Now I'm thinking with scalaz we could foldMap to good effect. EDIT: actually I guess we'd need something like scanMap. EDIT2: writing a scanMap using home-made monoids and functors would be fun, might do that tonight. experquisite Dec 13 '14 at 0:00

add a comment

up vote

4

down
vote

More straightforward version using foldLeft:

l1.foldLeft(List[Int]()){(acc, el) =>

if (acc.count(_ == el) >= 2) acc else el::acc}.reverse

share|improve this answer

answered Dec 13 '14 at 8:08

Paul

20.6k1059100

Ah, I see Daniel also has this. The prepend-then-reverse should make this a bit more efficient. Paul Dec 13 '14 at 8:10

2

These solutions using count can be quite inefficient (O(n^2)). Gbor Bakos Dec 13 '14 at 8:14

1

Yes, they can. It depends on the OP's context if this is a problem. They're also clear, which is also a good thing. Paul Dec 13 '14 at 8:20

add a comment

up vote

4

down vote

Similar to how distinct is implemeted, wi
th a multiset instead of a set:

def noMoreThan[T](list : List[T], max : Int) = {

val b = List.newBuilder[T]

val seen = collection.mutable.Map[T,Int]().withDefaultValue(0)

for (x <- list) {

if (seen(x) < max) {

b += x

seen(x) += 1

}

}

b.result()

}

share|improve this answer

edited Dec 26 '14 at 3:44

m-z

10.4k4936

answered Dec 13 '14 at 16:46

Jin

684

add a comment

up vote

3

down vote

Based on experquisite's answer, but using foldLeft:

def noMoreThanBis(xs: List[Int], max: Int) = {

val initialState:
(Map[Int, Int], List[Int]) = (Map().withDefaultValue(0), Nil)

val (_, result) = xs.foldLeft(initialState) { case ((count, res), x) =>

if (count(x) >= max)

(count, res)

else

(count.updated(x, count(x) + 1), x :: res)

}

result.reverse

}

share|improve this answer

answered Dec 13 '14 at 1:19

Dimitri

810513

add a comment

up vote

2

down vote

How about this:

list

.zipWithIndex

.groupBy(_._1)

.toSeq

.flatMap { _._2.take(2) }

.sortBy(_._2)

.map(_._1)

share|improve this answer

edited Dec 22 '14 at 19:15

answered Dec 22 '14 at 19:09

Dima

1,89326

add a comment

up vote

1

down vote

Here is a recursive solution (it will stack overflow for large lists):

def filterAfter[T](l: List[T], max: Int): List[T] = {

require(max > 1)

//keep the state of seen values

val seen = Map[T, Int]().withDefaultValue(0)//init to 0

def filterAfter(l: List[T], seen: Map[T, Int]): (List[T], Map[T, Int]) = {

l match {

case x :: xs =>

if (seen(x) < max) {

//Update the state and pass to next

val pair = filterAfter(xs, seen updated (x, seen(x) + 1))

(x::pair._1, pair._2)

} else {

//already seen more than max

filter
After(xs, seen)

}

case _ => (l, seen)//empty, terminate recursion

}

}

//call inner recursive function

filterAfter(l, seen, 2)._1

}

share|improve this answer

answered Dec 12 '14 at 23:50

Gbor Bakos

2,146719

Your recursive filterAfter don't need to return the state, you don't use it. Dimitri Dec 13 '14 at 1:35

@Dimitri you are right. It was after 0:00, so that was not my most creative moment. Gbor Bakos Dec 13 '14 at 8:11

add a comment

up vote

1

down vote

Its a bit ugly, but its relatively faster

val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1)

l1.foldLeft((Map[Int, Int](), List[Int](
))) { case ((m, ls), x) => {

val z = m + ((x, m.getOrElse(x, 0) + 1))

(z, if (z(x) <= 2) x :: ls else ls)

}}._2.reverse

Gives: List(1, 2, 3, 1, 3, 2, 5)

share|improve this answer