6

I'm trying to generate decent partition of given integer number N numbered K in lexicographical order, e.g. for N = 5, K = 3 we got:

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 4
5 = 2 + 3
5 = 5

And the third one is 1 + 1 + 3. How can I generate this without generating every partition(in C language, but most of all I need algorithm)?

Going to find maximal number in partition(assuming we can find number of partitions d[i][j], where i is number and j is maximal integer in its partition), then decrease the original number and number we are looking for. So yes, I'm trying to use dynamic programming. Still working on code.

This doesn't work at all:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


FILE *F1, *F2;


main()
{
    long long i, j, p, n, k, l, m[102][102];
    short c[102];
    F1 = fopen("num2part.in", "r");
    F2 = fopen ("num2part.out", "w");
    n = 0;
    fscanf (F1, "%lld %lld", &n, &k);
    p = 0;
    m[0][0] = 1;
    for ( i = 0; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            m[i][j] = m[i - j][j] + m[i][j - 1];
        }
        for (j = i + 1; j <= n; j++)
        {
            m[i][j] = m[i][i];
        }
    }
    l = n;
    p = n;
    j = n;
    while (k > 0)
    {
        while ( k < m[l][j])
        {
            if (j == 0)
            {
                while (l > 0)
                {
                    c[p] = 1;
                    p--;
                    l--;
                }
            break;
        }
        j--;
    }
    k -=m[l][j];
    c[p] = j + 1;
    p--;
    l -= c[p + 1];
    }
//printing answer here, answer is contained in array from c[p] to c[n]
}
Bergi
  • 630,263
  • 148
  • 957
  • 1,375
siziyman
  • 61
  • 3
  • Use dynamic programming to find number of (n,k)-partitions for n – zch Nov 20 '13 at 20:29
  • Trying to find maximal number in partition(assuming we can find number of partitions `d[i][j]`, where `i` is number and `j` is maximal integer in its partition), then decrease the original number and number we are looking for, still working on it. – siziyman Nov 20 '13 at 20:30

2 Answers2

3

Here is some example Python code that generates the partitions:

cache = {}
def p3(n,val=1):
    """Returns number of ascending partitions of n if all values are >= val"""
    if n==0:
        return 1 # No choice in partitioning
    key = n,val
    if key in cache:
        return cache[key]
    # Choose next value x
    r = sum(p3(n-x,x) for x in xrange(val,n+1))
    cache[key]=r
    return r

def ascending_partition(n,k):
    """Generate the k lexicographically ordered partition of n into integer parts"""
    P = []
    val = 1 # All values must be greater than this
    while n:
        # Choose the next number
        for x in xrange(val,n+1):
            count = p3(n-x,x)
            if k >= count:
                # Keep trying to find the correct digit
                k -= count
            elif count: # Check that there are some valid positions with this digit
                # This must be the correct digit for this location
                P.append(x)
                n -= x
                val = x
                break
    return P

n=5
for k in range(p3(n)):
    print k,ascending_partition(n,k)

It prints:

0 [1, 1, 1, 1, 1]
1 [1, 1, 1, 2]
2 [1, 1, 3]
3 [1, 2, 2]
4 [1, 4]
5 [2, 3]
6 [5]

This can be used to generate an arbitrary partition without generating all the intermediate ones. For example, there are 9253082936723602 partitions of 300. 

print ascending_partition(300,10**15)

prints

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 7, 8, 8, 11, 12, 13, 14, 14, 17, 17, 48, 52]
Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • Thanks, I have the code that generates all partitions, but there should be solution for generating one partition with decent number in this order(generating all works too slow). – siziyman Nov 20 '13 at 20:51
  • The code here generates a single partition at a time. You can simply call ascending_partition(n,k) with whatever values of n and k you desire. I just put in the loop for testing. – Peter de Rivaz Nov 20 '13 at 20:55
  • This still has the overhead of having to work through all the partitions, right? (as opposed to simply calculating the required one) – Bernhard Barker Nov 20 '13 at 21:58
  • @Dukeling No, I think the complexity is roughly O(n^3) and does not depend on k. The example shows it computing the partition for a huge value of k almost instantly. – Peter de Rivaz Nov 20 '13 at 22:02
0
def _yieldParts(num,lt):
  ''' It generate a comination set'''
  if not num:
    yield ()
  for i in range(min(num,lt),0,-1):
    for parts in _yieldParts(num-i,i):
      yield (i,)+parts


def patition(number,kSum,maxIntInTupple):
  ''' It generates a comination set with sum of kSum is equal to number
      maxIntInTupple is for maximum integer can be in tupple'''
  for p in _yieldParts(number,maxIntInTupple):
    if(len(p) <=kSum):
      if(len(p)<kSum):
        while len(p) < kSum:
          p+=(0,)
      print p


patition(40,8,40)

Output:
-------
(40,0,0,0,0,0,0,0)
(39,1,0,0,0,0,0,0)
. 
.
.
.
user3472760
  • 1
  • 1