Author |
Topic: Finding k-tuples of +ve integers that add up to N (Read 1094 times) |
|
singhar
Newbie
Posts: 22
|
 |
Finding k-tuples of +ve integers that add up to N
« on: Apr 20th, 2010, 6:09pm » |
 Quote  Modify
|
Given a positive integer N and another integer k (k <<< N) find all k-tuples of positive intgers such that the elements
of each tuple add up to N. e.g. if N = 5 and k = 3 then possible tuples are (1,1,3), (2,2,1) etc. Looking for a method
that will avoid repeatedly finding different permutations of the same tuple.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Finding k-tuples of +ve integers that add up t
« Reply #1 on: Apr 21st, 2010, 12:29am » |
Quote Modify
|
Then only look for ordered tuples. Once you've filled in the Jth element of the tuple, only allow later indices to have a value at most that large. You can go through them all efficiently using recursion.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Finding k-tuples of +ve integers that add up t
« Reply #2 on: Apr 21st, 2010, 9:25am » |
Quote Modify
|
Using towr's idea of recursion + monotonicity (C language implementation)
Code:
void integerPartitionEnumeration(int n, int k, int x[], int xLength,
int maxsofar) {
int i, j;
int* newBuffer;
if (n == 0 && k == 0) {
printIntegerArray(x, xLength);
} else if ((n == 0) ^ (k == 0)) {
return;
} else if (maxsofar > n || k > n) {
return;
} else {
for (i = max(1, maxsofar); i <= n; i++) {
newBuffer = malloc(sizeof(int) * (xLength + 1));
for (j = 0; j < xLength; j++) {
newBuffer[j] = x[j];
}
newBuffer[xLength] = i;
integerPartitionEnumeration(n - i, k - 1, newBuffer, xLength + 1, i);
free(newBuffer);
}
}
}
|
|
Code can most likely be improved; feel free suggest optimizations ...
Output for n=10, k=3:
1 1 8
1 2 7
1 3 6
1 4 5
2 2 6
2 3 5
2 4 4
3 3 4
|
| « Last Edit: Apr 21st, 2010, 11:30am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Finding k-tuples of +ve integers that add up t
« Reply #3 on: Apr 26th, 2010, 2:10am » |
Quote Modify
|
@wu, i guess instead of mallocing and freeing each time we can pass an array by reference having length k and can just overwrite the values once they are printed for one set.
something like this...
Code:
static void seq(int n, int k, int max, int [] arr){
if(k == 1){
arr[k-1] = n;
//print the array
for(int i=arr.length-1;i>=0;i--)System.out.print(arr[i] + " ");
System.out.println("");
return;
}
for(int i = max; i <= (n/k); i++){
arr[k-1] = i;
seq(n-i,k-1,i,arr);
}
}
|
|
|
| « Last Edit: Apr 26th, 2010, 2:10am by blackJack » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Finding k-tuples of +ve integers that add up t
« Reply #4 on: Apr 26th, 2010, 6:27am » |
Quote Modify
|
@blackjack: Thanks! That's a great suggestion. It's shorter now.
/* n = number to be partitioned.
* k = number of parts in the partition
* x[] = portion of the tuple found so far
* xLength = length of x[]
* maxsofar = largest number in tuple found so far
*/
Code:
void integerPartitionEnumeration(int n, int k, int** x, int xLength,
int maxsofar) {
int i;
if (n == 0 && k == 0) {
printIntegerArray(*x, xLength);
} else if ((n == 0) ^ (k == 0)) {
return;
} else if (maxsofar > n || k > n) {
return;
} else {
for (i = max(1, maxsofar); i <= n; i++) {
(*x)[xLength] = i;
integerPartitionEnumeration(n - i, k - 1, x, xLength + 1, i);
}
}
}
|
|
Note: The cases ((n == 0) ^ (k == 0)) and (maxsofar > n || k > n) stop the recursion because we know that it is impossible to find a partition if either situation occurs.
|
| « Last Edit: Apr 26th, 2010, 6:31am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print