Sunday 22 March 2015

Algorithms on partitioning



Hey everyone do you sense anything different? Well the Project Euler counter breezed from 166 to 175 in these one or two days, and it's like I can reach 200 or 225 without much difficulty. The main reason is that a new difficulty rating is out (it may not be new for you if you visit the site frequently though), and we can access to relatively easier later numbered question easier.

In fact many of them relies on the same searching technique or a number theory trick...here let's look at one of the classic algorithm and its variation:

We start from a classical example: In how many ways we can partition a number $n$ into sum of integers? (Don't cheat by looking at the OEIS!)




def f(n):
    count = 0
    queue = [(0,n+1)]
    #0: current sum = 0
    #n+1: n is the highest integer to be added
    while queue:
        (x,y) = queue[0]
        queue = queue[1:] #Can be optimaized using other heap structure
        for i in range(1,min(n-x+1,y)):
            if x+i == n:
                count += 1
            else:
                queue.append((x+i,i+1))
    return count

We sort the sum from the biggest integer to the lowest so that we won't count any combination twice. For example let's take $n=4$:

Step 1: The first integer can range from 1 to 4 so the queue is now
$queue = [(3,4),(2,3),(1,2)]$
$count = 1$
$(4,5)$ is already filled up so we simply add one to the count and we don't need to put them back to the queue.

Step 2: the first one $(4,5)$ is filled so we add one to the count. For $(3,4)$ the only possibility is to add 1 to it (and add to the count). Here we get
$count = 3$
$queue = [(3,2), (2,2)]$

Note that the only possibility to fill the last queuing instance $(2,2)$ is to fill the rest with ones (1+1+1+1), and we can only put one into the instance $(3,2)$, and therefore the total count is 5.

What about the number of partitions into distinct integers? (Yeah, the so called strict partition in OEIS). We just need a bit of modification:

def f(n):
    count = 0
    queue = [(0,n+1)]
    #0: current sum = 0
    #n+1: n is the highest integer to be added
    while queue:
        (x,y) = queue[0]
        queue = queue[1:] #Can be optimaized using other heap structure
        for i in range(1,min(n-x+1,y)):
            if x+i == n:
                count += 1
            else:
                queue.append((x+i,i))
    return count

Each time when we push the instance back into the queue we force the next integer to be added being smaller than the last one. It naturally vanish when you don't have enough integers to add up to $n$ (like, 5+2 but you want the sum to be 10).

Define non-square numbers to be numbers that is not divisible by any square number (except 1). How many non-square numbers can we find under $n$?

Recall that we can always translate multiplication into additions using the log function. Non-square numbers are simply product of distinct primes, so we have the following:

from math import log

def pgen(n): #Prime generator
    xs = range(n+1)
    xs[1] = 0
    for i in range(2,int(n**0.5)+1):
        if xs[i] != 0:
            for j in xrange(i*i,n+1,i):
                xs[j] = 0
    plist = []
    for i in xs:
        if i != 0:
            plist = [log(i)]+plist
    return plist

def f(n):
    target = log(n)
    count = 1 #1 is also a non-square number!
    ps = pgen(n)
    l = len(ps)
    queue = [(0,-1)]
    #0: current sum = 0
    #-1: start from the beginning
    while queue:
        (x,y) = queue[0]
        queue = queue[1:]
        for i in range(y+1,l):
            if x+ps[i] <= target:
                count += 1
                if i < l-1: #We can add another smaller prime
                    queue.append((x+ps[i],i))
    return count

This is a strict partition on some decimals (instead of integers), but once we translate the problem back to something we are familiar with it can be solved in a split second.

Given all the above algorithms, we should be able to solve the following:

Given a set of real numbers, find the number of strict partitions that sum up to $n$ so that each pair among the numbers chosen has a difference $r$.

This is actually related to one of the post-400 problem in Project Euler but I'm not going to disclose which problem it is :P

Talking about log function it can be used to locate the terms on the Fibonacci sequence (or other recurrence sequence). Consider the form

$F_n = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$

The second term is converging to zero so taking log we have

$n \approx \frac{\log (\sqrt{5}F_n)}{\log \phi}$

So I'll simply put two little problems here for readers to think about:

1) Write an algorithm for the following:
Input: Natural number $n$.
Output: Number of squared number (multiple of square number) but non-cube number (contain no factor of cubed number), e.g $12 = 2^2\times 3$.

2) Write an algorithm for the following:
Input: Integer $n$.
Output: If it is on the extended Fibonacci sequence ($\left\{ F_n\right\} _{n\in \mathbb{Z}}$) return the index (any one if it is on multiple indices) it is on, and return something else if it is not on the sequence.

No comments:

Post a Comment