Целочисленное разбиение в Scala

Question

Учитывая n (скажем, 3 человека) и s (скажем, 100 $), мы бы хотели разделить s среди 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, это занимает очень много времени, практически непригодно для использования.

Я ищу способы переделки своего кода с помощью отложенной оценки / Stream.

Мои требования: должно работать до 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

Вот быстрое и грязное решение 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 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 для комбинации.

Answer 3

Мое решение этой проблемы, он может компьютер 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