CODEWITHSUNDEEP
scalapartitioning
Andrew
Andrew

Reputation: 6394

Recursive integer partitioning algorithm

I am trying to count in how many ways I can partition an integer. So far I came up with the following function: 

def partition(num: Int): Int = {
    if(num == 1) return 1
    if(num <= 0) return 0
    return partition(num-1) + partition(num-(num-1))
}
partition(6) //6 instead of 7

E.g.: 5 -> 4 + 1, 3 + 2, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1

It returns 1 if num is 1 because I think partition(1) is the end.

Maybe you can spot the logic error in it?

Upvotes: 1

Views: 2049

Answers (5)

J&#252;rgen Strobel
J&#252;rgen Strobel

Reputation: 2248

def partition(n: Int): Int = {
    def partDecr(n: Int, decr: Int): Int = {
        if (n == 0) 1
        else if (n < 0 || decr == 0) 0
        else partDecr(n - decr, decr) + partDecr(n, decr - 1)
    }
    partDecr(n, n)
}
  • The inner function takes an extra parameter specifying the next possible decrement.
  • First it checks if we are at a valid end point (1 solution found).
  • Then it checks if we can go on (positive rest to partition, and positive decrement to try next).
  • Then it recurses into 2 ways:
    • The first "takes" the current decrement and reduces n by it,
    • The second "skips" the current decrement and will try with the next lower one.

Note this is not tail recursive and can use quite some stack space, but it is so slow it doesn't matter much.

Upvotes: 2

846846846
846846846

Reputation: 49

I think this works:

def partition(n: Int): Int = {
  def inner(n: Int, max: Int): Int =
    if (n == 0) 1
    else if (n < 0) 0
    else ((1 to max) map (x => inner(n - x, x))).sum

  if (n == 0) 0
  else inner(n, n-1)
}

An integer n can be partitioned into (n-1) + (any way of partitioning 1), (n-2) + (any way of partitioning 2), ..., 1 + (any way of partitioning (n-1)). However, naïvely computing partition(m) for m = 1 to n-1 and summing the results will count some methods of partitioning n twice, e.g. 1 + (n-1) and (n-1) + 1.

We can solve this problem by viewing a partition as a sequence of positive integers i{j} < n that sum to n, and only considering sequences that are ordered. The inner method has a max parameter that ensures it will only consider sequences with i{j} >= i{j+1}. So it will consider e.g. 2 + 1, but not 1 + 2.

n == 0 is an annoying edge case in the above code because you effectively don't want to count the empty sequence.

Upvotes: 4

huynhjl
huynhjl

Reputation: 41646

I think it requires another argument (the integers that can make up the partition, call it madeOf). That way you can divide the problem in 2 strictly smaller subsets. The count of partition(num, madeOf=(n, n-1, ..., 1)) is the sum of

  • partition(num, madeOf=(n-1, ..., 1)) (all the partitions that don't contain n)
  • partition(num-n, madeOf(n, n-1, ..., 1)) (all the partitions where there is at least one n)

You can then make it more optimal, since madeOf can be constructed from only one int:

def part(num: Int, madeOf: Int): Int =
  if (num == 0) 1 // we found a partition!
  else if (num < 0) 0 // no partition...
  else if (madeOf == 0) 0 // no more ways to make partition
  else part(num, madeOf - 1) +  // all the partitions that don't contain n
    part(num - madeOf, madeOf)  // all the partition that contain n

part(5, 4) // 6

Upvotes: 1

HamoriZ
HamoriZ

Reputation: 2438

You can use the following inner function - you only need to create a list with numbers < the number you want to partition. For example you want to partition 4, then intNumber should be (1,2,3,4)

  def partition(number: Int, intNumbers: List[Int]): Int = {    
if (number <= 0 || intNumbers.isEmpty) 
  0
else if ((number-intNumbers.head)==0) 
  1+partition(number-intNumbers.head,intNumbers)+partition(number,intNumbers.tail)
else 
  partition(number-intNumbers.head,intNumbers)+partition(number,intNumbers.tail)

Upvotes: 0

ziggystar
ziggystar

Reputation: 28688

I think there is no "that simple" algorithm to compute what you want. The presented algorithm in the OP won't work for a couple of reasons (which I won't discuss).

But I direct you to the Wikipedia entry on 'Partition', which also includes a recursive formula.

Notice, that this exact formula is both computationally more complex and also more complicated than the presented algorithm in the OP.

Upvotes: 1

Related Questions