Generazione della partizione intera tramite il numero

Question

Sto provando a generare una partizione decente del numero intero dato N numerato K in ordine lessicografico, ad es. per N = 5, K = 3 abbiamo ottenuto:

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 

E il terzo è 1 + 1 + 3. Come posso generare questo senza generare ogni partizione (in linguaggio C, ma soprattutto ho bisogno dell'algoritmo)?

Andare a trovare il numero massimo di partizioni (assumendo che siamo in grado di trovare il numero di partizioni d[i][j], dove i è il numero e j è intero massimale nella sua partizione), quindi diminuire il numero originale e il numero che stiamo cercando. Quindi sì, sto cercando di usare la programmazione dinamica. Sto ancora lavorando al codice.

Questo non funziona affatto:

#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] 
} 

Answer 1

Ecco qualche esempio di codice Python che genera le partizioni:

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) 

esso stampa:

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] 

Questo può essere utilizzato per generare una partizione arbitraria senza generare tutti quelli intermedi. Ad esempio, ci sono 9253082936723602 partizioni del 300.

print ascending_partition(300,10**15) 

stampe

[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] 

Answer 2

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) 
. 
. 
. 
.