2

给定 n（比如 3 个人）和 s（比如 100$），我们想在 n 个人中划分 s。

所以我们需要总和为 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，需要很长时间，实际上无法使用。

我正在寻找使用惰性评估/ Stream 来修改我的代码的方法。

我的要求：必须为 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

您需要动态编程或记忆化。还是一样的概念。

假设您必须将 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 回答
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 回答
1

我对这个问题的解决方案，它可以计算机 n 到 6：

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 回答