使用 scalacheck 生成排列

Question

我有一些像这样的生成器：

val fooRepr = oneOf(a, b, c, d, e)
val foo = for (s <- choose(1, 5); c <- listOfN(s, fooRepr)) yield c.mkString("$")

这会导致重复...我可能会得到两个 a 等。我真正想要的是生成恰好 0 或 1 或每个 a、b、c、d 或 e 的随机排列（至少其中之一），以任何顺序。

我想一定有一个简单的方法，但我正在努力寻找一个困难的方法。 :)

编辑：好的，这似乎有效：

val foo = for (s <- choose(1, 5);
               c <- permute(s, a, b, c, d, e)) yield c.mkString("$")

def permute[T](n: Int, gs: Gen[T]*): Gen[Seq[T]] = {
  val perm = Random.shuffle(gs.toList)
  for {
    is <- pick(n, 1 until gs.size)
    xs <- sequence[List,T](is.toList.map(perm(_)))
  } yield xs
}

...大量借鉴 Gen.pick。

谢谢你的帮助，-埃里克

Answer 1

Rex，感谢您准确地澄清了我想要做的事情，这是有用的代码，但对于 scalacheck 来说可能不太好，特别是如果所讨论的生成器非常复杂的话。在我的特定情况下，生成器 a、b、c 等生成巨大的字符串。

无论如何，我上面的解决方案有一个错误；对我有用的是下面的。我在 github 上放置了一个小项目来演示如何执行此操作，

其内容如下。如果有更好的方法，我很想知道......

package powerset

import org.scalacheck._
import org.scalacheck.Gen._
import org.scalacheck.Gen
import scala.util.Random

object PowersetPermutations extends Properties("PowersetPermutations") {

  def a: Gen[String] = value("a")

  def b: Gen[String] = value("b")

  def c: Gen[String] = value("c")

  def d: Gen[String] = value("d")

  def e: Gen[String] = value("e")

  val foo = for (s <- choose(1, 5);
                 c <- permute(s, a, b, c, d, e)) yield c.mkString

  def permute[T](n: Int, gs: Gen[T]*): Gen[Seq[T]] = {
    val perm = Random.shuffle(gs.toList)
    for {
      is <- pick(n, 0 until gs.size)
      xs <- sequence[List, T](is.toList.map(perm(_)))
    } yield xs
  }

  implicit def arbString: Arbitrary[String] = Arbitrary(foo)

  property("powerset") = Prop.forAll {
    a: String => println(a); true
  }
}

谢谢，
埃里克

Answer 2

您不是在描述排列，而是描述幂集（减去空集）编辑：您正在描述幂集和排列的组合。索引集合 N 的幂集与 2^N 同构，因此我们简单地（仅在 Scala 中；也许您想更改它以便与 ScalaCheck 一起使用）：

def powerSet[X](xs: List[X]) = {
  val xis = xs.zipWithIndex
  (for (j <- 1 until (1<<xs.length)) yield {
    for ((x,i) <- xis if ((j & (1<<i)) != 0)) yield x
  }).toList
}

生成给定集合的所有可能子集。当然，如果原始集合包含多个元素，则显式生成幂集是不明智的。如果您不想生成所有这些，只需传入从 1 到 (1<<(xs.length-1)) 的随机数并运行内循环。 （如果有 33-64 个元素，则切换到 Long；如果还有更多元素，则切换到 BitSet。）然后，如果您愿意，可以对结果进行排列以切换顺序。

---

编辑：如果您可以轻松生成排列并且可以添加虚拟参数，那么还有另一种方法可以做到这一点：使用 Stop 标记使您的列表更长。然后排列并 .takeWhile(_ != Stop)。哒哒！任意长度的排列。 （如果需要的话，过滤掉零长度答案。）