4

私はこのようないくつかのジェネレータを持っています:

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

これは重複につながります... 2 つの a などを取得する可能性があります。本当に必要なのは、正確に 0 または 1、または a、b、c、d、または e のそれぞれ (少なくとも 1 つの何か) を使用してランダム順列を生成することです。 、任意の順序で。

簡単な方法があるに違いないと思っていましたが、難しい方法を見つけるのに苦労しています。:)

編集：わかりました、これはうまくいくようです：

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ます。

助けてくれてありがとう、-エリック

4

2 に答える 2

3

順列を記述しているのではなく、べき集合（空の集合を差し引いたもの）編集：べき集合と順列の組み合わせを記述しています。インデックス付きセット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))、内部ループを実行します。（Long33〜64個の要素がある場合はに切り替え、さらにある場合はに切り替えBitSetます。）次に、結果を並べ替えて、必要に応じて順序を切り替えることができます。

編集：順列を簡単に生成でき、ダミーの引数を追加できる場合は、これを行う別の方法がありStopます。トークンを使用して、リストを1つ長くします。次に、順列と.takeWhile(_ != Stop)。タダ！任意の長さの順列。（必要に応じて、長さゼロの回答を除外します。）

于 2011-02-24T17:02:57.717 に答える
3

レックス、私がやろうとしていることを正確に明確にしてくれてありがとう。それは便利なコードですが、問題のジェネレーターが非常に複雑な場合は特に、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
  }
}

ありがとう、エリック

于 2011-02-24T22:20:44.870 に答える