title: Generating integer partition by its number
body: <p>I'm trying to generate decent partition of given integer number <code>N</code> numbered <code>K</code> in lexicographical order, e.g. for  <code>N = 5, K = 3</code> we got:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>And the third one is <code>1 + 1 + 3</code>.
  How can I generate this without generating every partition(in C language, but most of all I need algorithm)?</p>
  
  <p>Going to find maximal number in partition(assuming we can find number of partitions <code>d[i][j]</code>, where <code>i</code> is number and <code>j</code> 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.</p>
  
  <p>This doesn't work at all:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  
  
  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", &amp;n, &amp;k);
      p = 0;
      m[0][0] = 1;
      for ( i = 0; i &lt;= n; i++)
      {
          for (j = 1; j &lt;= i; j++)
          {
              m[i][j] = m[i - j][j] + m[i][j - 1];
          }
          for (j = i + 1; j &lt;= n; j++)
          {
              m[i][j] = m[i][i];
          }
      }
      l = n;
      p = n;
      j = n;
      while (k &gt; 0)
      {
          while ( k &lt; m[l][j])
          {
              if (j == 0)
              {
                  while (l &gt; 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]
  }
  </code></pre>