Scala best way to make uniform crossover operation with permutation list?

Question

I search the best and the most elegant way to make GA crossover operator in Scala functional (No "for" loop, with only immutable type if possible), for example, with this list:

val A = IndexedSeq (5,4,8)
val B = IndexedSeq (3,2,6)

I want to make random bitcoin permutation (with rng.nextBoolean for example) between each element in my IndexedSeq, and finally I get the two lists A' and B' after permutation of their elements.

Example of execution:

rng.nextBoolean <- (true,false,true)
A' = 3,4,6
B' = 5,2,8

Thanks.

Saying _permutations_ you mean randomly swapping elements between lists? — om-nom-nom, Nov 29 '11 at 16:08
Can you give an example of the output you're expecting please? — Matthew Farwell, Nov 29 '11 at 16:13

Luigi Plinge · Accepted Answer · 2011-11-29T20:42:58.927

4

def crossover[T](a: Seq[T], b: Seq[T], rs: Seq[Boolean]) =
  (a, b, rs).zipped.map((x, y, z) => if (z) Seq(x, y) else Seq(y, x)).transpose

Use with Booleans as third argument:

scala> val Seq(a1, b1) = crossover(A, B, List(true, false, true))
a1: Seq[Int] = Vector(5, 2, 8)
b1: Seq[Int] = Vector(3, 4, 6)

If you want it with a default sequence of Booleans, you could provide a default argument like this:

def crossover[T](a: Seq[T], b: Seq[T], rs: Seq[Boolean] = { 
                                       val rng = new util.Random
                                       Stream.continually(rng.nextBoolean) }) =
  (a, b, rs).zipped.map((x, y, z) => if (z) Seq(x, y) else Seq(y, x)).transpose

edited Nov 29 '11 at 20:42

answered Nov 29 '11 at 17:01

Luigi Plinge

50,650
20
113
180

I like your approach because it externalizes the randomness(more functional, side effect free). So you can choose to determine randomness at call side or don't worry and call the method with default parameter. – Peter Schmitz Nov 29 '11 at 18:38
Which Scala version are you using? With Scala 2.9.1 it doesn't compile, except you change `crossover[T](a: Seq[T], b: Seq[T], rs: Seq[Boolean] = ...)` to `crossover[T](a: Seq[T], b: Seq[T])(rs: Seq[Boolean] = ...)`. – Peter Schmitz Nov 29 '11 at 18:51
@PeterSchmitz Thanks - it turns out my REPL namespace was polluted, which is why it worked for me. Have updated. Default argument is trickier than I thought since you'd need to call it with `crossover(A, B)()` which is a bit ugly. – Luigi Plinge Nov 29 '11 at 20:17
Thanks a lot, it's a great approach :) Thanks also to other contributors for your answer! – reyman64 Nov 30 '11 at 10:16

score 4 · Answer 2 · answered Dec 01 '11 at 15:59

4

Wow, where's all this code coming from? Here:

val (a1, b1) = A zip B map (t => if (util.Random.nextBoolean) t.swap else t) unzip

There, that's all.

If you already have a list of random booleans, you can do this:

val (a1, b1) = A zip B zip C map { case (t, flag) => if (flag) t.swap else t } unzip

answered Dec 01 '11 at 15:59

Daniel C. Sobral

295,120
86
501
681

Great! Simple and clear! One more example one should know the scala API by heart. – Peter Schmitz Dec 05 '11 at 10:06

score 1 · Answer 3 · edited Nov 29 '11 at 16:33

import scala.util.Random

val A = IndexedSeq(5,4,8)
val B = IndexedSeq(3,2,6)

def crossover[T](rng: Random)(a: Seq[T], b: Seq[T]): (Seq[T],Seq[T]) = {
  if (a.isEmpty && b.isEmpty) return (Nil,Nil)
  val (aTailCrossover,bTailCrossover) = crossover(rng)(a.tail,b.tail)
  if (rng.nextBoolean) (b.head +: aTailCrossover, a.head +: bTailCrossover)
    else               (a.head +: aTailCrossover, b.head +: bTailCrossover)
}

println(crossover(new Random)(A,B))

user unknown · Answer 4 · 2011-11-29T22:19:20.197

def rndCombi [T] (a: Seq[T], b: Seq[T]): Seq[T] = {
  if (a.size != b.size) sys.error ("sizes don't match: a:" + a.size +  " != b: " + b.size) 
  val rnd = util.Random 
  val max = (math.pow (2, a.size)).toInt
  val r = rnd.nextInt (max)

  def pick (a: Seq[T], b: Seq[T], r: Int) : List[T] = {
    if (a.size == 0) Nil else 
    if (r % 2 == 0) a.head :: pick (a.tail , b.tail, r/2) else 
    b.head :: pick (a.tail , b.tail, r/2)
  }

  // print all combinations for testing:
  // (0 until max).map (i => println (pick (a, b, i).mkString ("-")))

  pick (a, b, r).toSeq
}
// I choosed different values for easy testing:
val a = IndexedSeq (7, 8, 9)
val b = IndexedSeq (1, 2, 3)

println (rndCombi (a, b).mkString (" "))
println (rndCombi (a, b.tail).mkString (" "))

Initializing util.Random each time is of course not very clever, if done frequently. So for production code you would rearrange the code.

If you don't restrict the input to 2 sequences, it get's more interesting. Here we go:

def rndCombi [T] (s: Seq[Seq[T]]): Seq[T] = {

  val outer = s.size 
  val inner = s(0).size 
  val rnd = util.Random 
  val max = (math.pow (outer, inner)).toInt
  val r = rnd.nextInt (max)

  def pick (s: Seq[Seq[T]], r: Int, pos: Int = 0) : List[T] =
    if (pos == inner) Nil 
    else s(r % inner)(pos) :: pick (s, r/inner, pos + 1) 

  // print all combinations for testing:
  (0 until max).map (i => println (pick (s, i).mkString ("-")))  
  println ()
  pick (s, r).toSeq
}

val a = IndexedSeq (1, 2, 3)
val b = IndexedSeq (4, 5, 6)
val c = IndexedSeq (7, 8, 9)

println (rndCombi (Seq (a, b, c)).mkString (" "))

The second solution can, of course, be used for 2 sequences as well.

Scala best way to make uniform crossover operation with permutation list?

4 Answers4

Linked