2

n (たとえば 3 人) と s (たとえば 100$ ) が与えられた場合、s を n 人に分割したいと思います。

したがって、合計が s になるすべての可能な n タプルが必要です。

以下の私のScalaコード：

def weights(n:Int,s:Int):List[List[Int]] = {
     List.concat( (0 to s).toList.map(List.fill(n)(_)).flatten, (0 to s).toList).
     combinations(n).filter(_.sum==s).map(_.permutations.toList).toList.flatten
}

println(weights(3,100))

これは n の値が小さい場合に機能します。( n=1、2、3 または 4)。

n=4 を超えると、非常に時間がかかり、実質的に使用できなくなります。

遅延評価/ストリームを使用してコードを作り直す方法を探しています。

私の要件：nから10まで動作する必要があります。

警告 : 問題は非常に急速に大きくなります。Matlab からの私の結果 -

---For s =100, n = 1 thru 5 results are ---
n=1 :1 combinations
n=2 :101 combinations
n=3 :5151 combinations
n=4 :176851 combinations
n=5: 4598126 combinations
---
4

3 に答える 3

2

迅速で汚いStream解決策は次のとおりです。

 def weights(n: Int, s: Int) = (1 until s).foldLeft(Stream(Nil: List[Int])) {
   (a, _) => a.flatMap(c => Stream.range(0, n - c.sum + 1).map(_ :: c))
 }.map(c => (n - c.sum) :: c)

n = 6私のマシンでは約15秒で動作します：

scala> var x = 0
scala> weights(100, 6).foreach(_ => x += 1)
scala> x
res81: Int = 96560646

補足として、 に到達するまでに、これらのものn = 10が4,263,421,511,271あります。ストリーミングするだけで何日もかかります。

于 2011-10-26T00:24:29.683 に答える
2

動的プログラミング、またはメモ化が必要です。とにかく、同じコンセプト。

s を n で割る必要があるとしましょう。再帰的に、これは次のように定義されます。

def permutations(s: Int, n: Int): List[List[Int]] = n match {
  case 0 => Nil
  case 1 => List(List(s))
  case _ => (0 to s).toList flatMap (x => permutations(s - x, n - 1) map (x :: _))
}

さて、これはまだ地獄のように遅くなりますが、ここに問題があります...permutations(s, n)すでに計算した数値を再計算する必要はありません。したがって、代わりにこれを行うことができます：

val memoP = collection.mutable.Map.empty[(Int, Int), List[List[Int]]]
def permutations(s: Int, n: Int): List[List[Int]] = {
  def permutationsWithHead(x: Int) = permutations(s - x, n - 1) map (x :: _)

  n match {
    case 0 => Nil
    case 1 => List(List(s))
    case _ => 
      memoP getOrElseUpdate ((s, n), 
                             (0 to s).toList flatMap permutationsWithHead)
  }
}

これは、すべての順列を計算するため、さらに改善することができます。すべての組み合わせを計算し、再計算せずに並べ替えるだけで済みます。

すべての組み合わせを計算するには、次のようにコードを変更します。

val memoC = collection.mutable.Map.empty[(Int, Int, Int), List[List[Int]]]
def combinations(s: Int, n: Int, min: Int = 0): List[List[Int]] = {
  def combinationsWithHead(x: Int) = combinations(s - x, n - 1, x) map (x :: _)

  n match {
    case 0 => Nil
    case 1 => List(List(s))
    case _ => 
      memoC getOrElseUpdate ((s, n, min), 
                             (min to s / 2).toList flatMap combinationsWithHead)
  }
}

combinations(100, 10)組み合わせの数だけを考えると、実行はまだ遅いです。各組み合わせの順列は、組み合わせを呼び出すだけで取得できます.permutation。

于 2011-10-26T00:07:34.710 に答える
1

この問題の私の解決策、それは 6 まで n を計算できます:

object Partition {
  implicit def i2p(n: Int): Partition = new Partition(n)
  def main(args : Array[String]) : Unit = {
    for(n <- 1 to 6) println(100.partitions(n).size)
  }

}

class Partition(n: Int){
  def partitions(m: Int):Iterator[List[Int]] = new Iterator[List[Int]] {
    val nums = Array.ofDim[Int](m)
    nums(0) = n

    var hasNext = m > 0 && n > 0

    override def next: List[Int] = {
      if(hasNext){
        val result = nums.toList
        var idx = 0
        while(idx < m-1 && nums(idx) == 0) idx = idx + 1
        if(idx == m-1) hasNext = false
        else {
          nums(idx+1) = nums(idx+1) + 1
          nums(0)     = nums(idx) - 1
          if(idx != 0) nums(idx)   = 0
        }
        result
      }
      else Iterator.empty.next
    }
  }
}

1 101 5151 176851 4598126 96560646

ただし、可能なnタプルの数を表示することはできます:

val pt: (Int,Int) => BigInt =  {
    val buf = collection.mutable.Map[(Int,Int),BigInt]()
    (s,n) => buf.getOrElseUpdate((s,n),
        if(n == 0 && s > 0) BigInt(0)
        else if(s == 0) BigInt(1)
        else (0 to s).map{k => pt(s-k,n-1)}.sum
        )
  }

  for(n <- 1 to 20) printf("%2d :%s%n",n,pt(100,n).toString)

 1 :1
 2 :101
 3 :5151
 4 :176851
 5 :4598126
 6 :96560646
 7 :1705904746
 8 :26075972546
 9 :352025629371
10 :4263421511271
11 :46897636623981
12 :473239787751081
13 :4416904685676756
14 :38393094575497956
15 :312629484400483356
16 :2396826047070372396
17 :17376988841260199871
18 :119594570260437846171
19 :784008849485092547121
20 :4910371215196105953021
于 2011-10-26T05:02:40.033 に答える