-1

I am looking for a program which will have as input n representing an integer number and k the number of integer numbers n is supposed to be the sum of.

For example n = 5, k =2 will have as output

1 + 4, 3 + 2.

I have searched the internet but all I have found is a program that finds some options but will not show what options.

I do not care which language the program is written on as long as it does what I want.

netanel
  • 1
  • Have you considered this [**Stack Overflow answer**](https://stackoverflow.com/questions/41011408/split-a-number-n-as-sum-of-k-distinct-numbers/41011688)? –  Feb 05 '20 at 09:44
  • Your problem is to find all [partitions](https://en.wikipedia.org/wiki/Partition_(number_theory)) of n into k parts. You can find a Python solution which finds all ordered partitions (i.e. where the order matters) in [this answer](https://stackoverflow.com/questions/58915599/generate-restricted-weak-integer-compositions-or-partitions-of-an-integer-n-in/59131521#59131521), by calling `constrained_partitions(n, k, 1, n)`. Or search for *partition n into k parts algorithm* on Google. – kaya3 Feb 05 '20 at 18:52
  • @DarshanPatil Obviously the complexity will be at least as much as the size of the output required, which will be enormous for large `n`. That is inherent in the question. The answer I linked to only produces 0s in the output when you ask for 0s to be allowed, by calling it with `min_elem` equal to 0; if you call it with `min_elem` equal to 1 then it will not include 0s in the output. – kaya3 Sep 22 '21 at 11:16
  • @DarshanPatil Yes, I specifically said the answer I linked to was for *"ordered partitions (i.e. where the order matters)"*. Please read more carefully; there was no need to @ tag me here. – kaya3 Sep 22 '21 at 11:24

1 Answers1

0

Partition of Integer into k parts: p(n, k)

#include<stdio.h>
#include<math.h>
int x=1;
void array_print(int p[], int n, int u,int y,int d)
{
    int i,s=0,l=u;
    int m=d;
    int j=1;
    if(n<=l)   
    for(i=0;i<l;i++)
    {
        s += p[i];
        j=j*p[i];
    }
    if(j>0&&s==y)
    {
         printf("%d] ",x++);
         for (i=0;i<l;i++)
         printf("%d ",p[i]);
     printf("\n");
}
}
void P(int n,int l)
{
    int p[n];
    int t=n;
    int k = 0;
    int g=0;
    p[k] = n;
    int r;
    int f=1,e,x;
    while (1)
    {
        if(k+1<=l)
        {
            for(e=0;e<l;e++)
                x += p[e];
            if(x==t)
                f++;
        }
        array_print(p, k+1,l,t,f);
        r= 0;
        while (k >= 0 && p[k] == 1)
        {
            r += p[k];
            k--;
        }
        if (k < 0)  return;
        p[k]--;
        r++;
        while (r > p[k])
        {
            p[k+1] = p[k];
            r = r- p[k];
            k++;
        }
        p[k+1] = r;
        k++;
    }
}
int main()
{
    int num,l;
    printf("\nEnter a number to perform integer partition: ");
    scanf("%d", &num);
    printf("\nEnter parts of form: \n");
    scanf("%d",&l);
    P(num,l);
    printf("p(%d, %d)=%d", num, l, x-1);
    return 0;
}

  • Console

    Enter a number to perform integer partition: 7 
Enter parts of form: 3
1] 5 1 1 
2] 4 2 1 
3] 3 3 1 
4] 3 2 2 
p(7, 3)=4

The above code was made with intention of partition of integer: p(n) However, Can also print: p(n,k)

But I personally would suggest to use Euler's Identity on Partition of Integer:

p(n,k) = p(n,k-1) + p(n-k, k) where p(n,k=n or k=1)=1

And the same triangle can be completed.

One of the beautiful problems from Number-Theory.