Scala使用排列列表进行统一交叉操作的最佳方法？

Question

我搜索在 Scala 中使 GA 交叉运算符起作用的最佳和最优雅的方法（没有“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

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 2

哇，这些代码从哪里来？这儿：

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 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 个序列。