Division into k parts

Question

I am programming in java and I need to formulate an algorithm. The requirements of the algorithm are:

• We have 3 integer variables n , m , k ;
• We want to divide n into parts of k so that the sum of the k parts is equal to n , and each part is an integer between 1 and m .
• We need all possible combinations with valid integers.

For example, with a set of input data:

 n = 7; m = 3; k = 4 

we have two different combinations that we can formulate:

 7 = 2 + 2 + 2 + 1 

and

 7 = 3 + 2 + 1 + 1 

Thank you all.

Answer 1

The idea is the approach of the reverse lookup algorithm (with recursion), you can reduce the parameters and get solutions for partial solutions, and then check if you have the right solution.

 public class Problem { private static void algorithm(int n, int k, int m) { algorithmRecursive(Collections.EMPTY_LIST, n, k, m, 1); } private static void algorithmRecursive(List<Integer> partial, int n, int k, int m, int min) { if ( (k > 0) ) { // Optimization if ((n <= k * m) && (n >= k*min)){ for (int i = min; i <= Math.min(m, n); i++) { List<Integer> newPartial = new ArrayList<>(partial); newPartial.add(i); algorithmRecursive(newPartial, n - i, k - 1, m, i); } } } else if (n == 0) { // Right solution System.out.println(partial); } } public static void main(String[] args) { algorithm(7,4,3); } } 

Answer 2

To get the "number of divisions" counter, you can use Dynamic Programming , which follows the recursive formula:

 D(0,0,j) = 1 D(x,0,j) = 0 x > 0 D(x,i,j) = 0 x < 0 or j<0 D(x,i,j) = D(xj,i-1,j) + D(x,i,j-1) 

The answer denoted by D(n,k,m) is the number of such divisions.
Difficulty O(n*k*m)

Java Code:

 public static int numDivisions(int n, int m, int k) { int[][][] D = new int[n+1][k+1][m]; for (int j = 0; j < m; j++) { for (int x = 0; x <= n; x++) { D[x][0][j] = 0; } D[0][0][j] = 1; } for (int i = 1; i <= k; i++) { for (int x = 0; x <= n; x++) { for (int j = 0; j < m; j++) { D[x][i][j] = 0; if (j > 0) D[x][i][j] += D[x][i][j-1]; if (xj-1 >=0) D[x][i][j] += D[xj-1][i-1][j]; } } } return D[n][k][m-1]; } 

As a side note, this seems like a stars and bars problem, but the order doesn't matter here, and besides that, you have the top one related to the number of “stars” in the cell.

Answer 3

I believe this can be done easily with recursion. First check if it is possible to split n at all, that is, when n<=m*k && n>=k , if not, returns an empty array.

If it is divisible, sequentially select m' from the range [1..m] and select it as the first number, then recursively select the rest for the parameters n'=n-'m, m'=m', k'=k-1 , then we will return all the results.

Recursion will successfully stop only for n=0 and k=0 . The complexity of the time should be the same as the size of the output.