Scala中的整數分區

Question

給定n（比如說3個人）和s（比如100 $），我們想要在n個人中進行劃分。

因此，我們需要所有可能的n元組那筆S下方

我的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 
--- 

Answer 1

你需要dynamic programming，或memoization。無論如何，同樣的概念。

假設你必須在n之間劃分s。遞歸，這是這樣定義的：現在

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獲得。

Answer 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。這隻需要幾天就可以完成。

Answer 3

我這個問題的解決方案，它可以在計算機ñ至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 
    } 
    } 
} 

---

但是，我們可以只顯示號碼可能的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