On Jul 12, 10:56 am, Tech Id <[email protected]> wrote:
> This can be done by recursion.
>
> Each number can be represented as:
>
> N =>
> 1) (N-1), 1
> 2) (N-2), 2
> 3) (N-3), 3
> ....
> N) (1), (N-1)
>
> For each number (N-k), repeat the above in recursion.
You have the right idea, but this recursion scheme will produce many
repeats. Once you have chosen 1 for the right hand operand, for
example, you can avoid repeats by requiring that all other numbers in
the partition be 1 or greater.
Here is C code that implements this strategy. Note I am assuming 0's
are okay in the partition. If 1 is the minimum, then just change the
line in main to
part(10, 4, 1);
-----------
#include <stdio.h>
char buf[1024];
int bp;
void part(int n, int m, int min)
{
int i;
if (m == 0 && n == 0) {
for (i = bp - 1; i >= 0; i--) printf("%d ", buf[i]);
printf("\n");
}
else if (m > 0) {
for (i = min; i <= n; i++) {
buf[bp++] = i;
part(n - i, m - 1, i);
bp--;
}
}
}
int main(void)
{
part(10, 4, 0);
return 0;
}
> ./a.out
10 0 0 0
9 1 0 0
8 2 0 0
7 3 0 0
6 4 0 0
5 5 0 0
8 1 1 0
7 2 1 0
6 3 1 0
5 4 1 0
6 2 2 0
5 3 2 0
4 4 2 0
4 3 3 0
7 1 1 1
6 2 1 1
5 3 1 1
4 4 1 1
5 2 2 1
4 3 2 1
3 3 3 1
4 2 2 2
3 3 2 2
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
