Clash Royale CLAN TAG

Generate a list of Tuple2 objects meeting some conditions

I want to generate a list of Tuple2 objects. Each tuple (a,b) in the list should meet the following 4 conditions:

list

Tuple2 objects

(a,b)

a

b

b>a

a/b

1/30

a

b

Number N

N

BigInt

How to write a scala function to generate the List of Tuples meeting the above requirements?( Even better if the a and b lies in a given interval (N1,N2) where N2>N1 instead of above 4th condition)

scala function

the List of Tuples

a

b

interval (N1,N2)

N2>N1

This is my attempt..may be it is fine for Ints and Longs..But for BigInt there is sqrt problem I am facing..Please correct if I am wrong in my approach in coding as below:

scala> def genTups(N:Long) ={
| val x = for(s<- 1L to Math.sqrt(N).toLong) yield s*s;
| val y = x.combinations(2).map{ case Vector(a,b) => (a,b)}.toList
| y.filter(t=> (t._1*30/t._2)>=1)
| }
genTups: (N: Long)List[(Long, Long)]

scala> genTups(30)
res32: List[(Long, Long)] = List((1,4), (1,9), (1,16), (1,25), (4,9), (4,16), (4,25), (9,16), (9,25), (16,25))


Improved this using BigInt square-root algorithm as below:

def genTups(N1:BigInt,N2:BigInt) ={
def sqt(n:BigInt):BigInt = {
var a = BigInt(1)
var b = (n>>5)+BigInt(8)
while((b-a) >= 0) {
var mid:BigInt = (a+b)>>1
if(mid*mid-n> 0) b = mid-1
else a = mid+1
}; a-1 }
val x = for(s<- sqt(N1) to sqt(N2)) yield s*s;
val y = x.combinations(2).map{ case Vector(a,b) => (a,b)}.toList
y.filter(t=> (t._1*30/t._2)>=1)
}


I invite any improvements in my algo or any limitations/lapses in this algorithm.

case

combinations

a

<b

map

2 Answers
2

You can avoid sqrt in you algorithm by changing the way you calculate x to this:

sqrt

x

val x = (BigInt(1) to N).map(x => x*x).takeWhile(_ <= N)


The final function is then:

def genTups(N: BigInt) = {
val x = (BigInt(1) to N).map(x => x*x).takeWhile(_ <= N)
val y = x.combinations(2).map { case Vector(a, b) if (a < b) => (a, b) }.toList
y.filter(t => (t._1 * 30 / t._2) >= 1)
}


You can also re-write this as a single chain of operations like this:

def genTups(N: BigInt) =
(BigInt(1) to N)
.map(x => x * x)
.takeWhile(_ <= N)
.combinations(2)
.map { case Vector(a, b) if a < b => (a, b) }
.filter(t => (t._1 * 30 / t._2) >= 1)
.toList


In a quest for performance, I came up with this recursive version that appears to be significantly faster

def genTups(N1: BigInt, N2: BigInt) = {
def sqt(n: BigInt): BigInt = {
var a = BigInt(1)
var b = (n >> 5) + BigInt(8)
while ((b - a) >= 0) {
var mid: BigInt = (a + b) >> 1
if (mid * mid - n > 0) {
b = mid - 1
} else {
a = mid + 1
}
}
a - 1
}

@tailrec
def loop(a: BigInt, rem: List[BigInt], res: List[(BigInt, BigInt)]): List[(BigInt, BigInt)] =
rem match {
case Nil => res
case head :: tail =>
val a30 = a * 30
val thisRes = rem.takeWhile(_ < a30).map(b => (a, b))

loop(head, tail, thisRes.reverse ::: res)
}

val squares = (sqt(N1) to sqt(N2)).map(s => s * s).toList

loop(squares.head, squares.tail, Nil).reverse
}


Each recursion of the loop adds all the matching pairs for a given value of a. The result is built in reverse because adding to the front of a long list is much faster than adding to the tail.

a

takeWhile()

.view

.map

Vector

Seq

Firstly create a function to check if number if perfect square or not.

def squareRootOfPerfectSquare(a: Int): Option[Int] = {
val sqrt = math.sqrt(a)
if (sqrt % 1 == 0)
Some(sqrt.toInt)
else
None
}


Then, create another func that will calculate this list of tuples according to the conditions mentioned above.

def generateTuples(n1:Int,n2:Int)={
for{
b <- 1 to n2;
a <- 1 to n1 if(b>a && squareRootOfPerfectSquare(b).isDefined && squareRootOfPerfectSquare(a).isDefined)
} yield ( (a,b) )
}


Then on calling the function with parameters generateTuples(5,10)
you will get an output as

generateTuples(5,10)


res0: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,4), (1,9), (4,9))


Hope that helps !!!

generateTuple

squareRootOfPerfectSquare

BigInt

sqrt

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.