Scala лучший способ сделать равномерную операцию кроссовера со списком перестановок?

Question

Я ищу лучший и самый элегантный способ сделать оператор кроссовера GA в Scala функциональным (без цикла «for», если возможно, только с неизменяемым типом), например, с помощью этого списка:

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

Я хочу сделать случайную перестановку биткойнов (например, rng.nextBoolean) между каждым элементом в моем IndexedSeq, и, наконец, я получаю два списка A и B после перестановки их элементов.

Пример выполнения:

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

Спасибо.

Answer 1

Ух ты, откуда весь этот код?Здесь:

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

Вот и все.

Если у вас уже есть список случайных логических значений, вы можете сделать это:

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

Answer 2

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

Использование с логическими значениями в качестве третьего аргумента:

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)

Если вы хотите использовать последовательность логических значений по умолчанию, вы можете указать аргумент по умолчанию, например:

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

Answer 3

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

Answer 4

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

Инициализация util.Random каждый раз, конечно, не очень умно, если это делается часто.Таким образом, для производственного кода вы должны изменить код.

Если вы не ограничите ввод 2 последовательностями, это станет более интересным.Здесь мы идем:

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

Второе решение, конечно, можно использовать и для 2 последовательностей.