I guess a simple backtracking problem
 

I want to make a small program that doe the following:
I read a variable k= an the program generates the following:

for k=6

0 0 0 0 6
0 0 0 6 0
0 0 6 0 0
.....
0 0 0 5 1
0 0 1 0 5
.....
and so on
the program has to generate an array with 5 component that summed equals k, and it has to arrange them in all the possibilities.
Sorry for my math-english :)
I`m sorry if this is kinda` lame question but I can't figure it out. I'm new to this field. Maybe you can help me with some hints or with some pieces of code in C/C++.
Thanx a lot and again sorry.

you lost me with the pattern on the second part with the 5's and 1's

He needs to generate a matrix that contains every possibility where the sum of each row equals the variable K.

0 0 0 0 6 == 0+0+0+0+6=6
0 0 0 6 0 == 0+0+0+6+0=6
.
.
.
1 1 1 1 2 == 1+1+1+1+2=6

and so on...

that is exacly what i mean... could you help me ?

Would we be doing your school/university homework?
(if not, I apologize for asking)

nope... a friend ask me to help him and make a program. The program is bigger than this it includes other pieces of code. I was only stoped by this problem.

just iterate through all the numbers from 00000 to 99999 and sum their digits one by one, if they pass, keep them. I can do this in python in one line (but it's ugly as hell and I wouldn't recommend doing it all on one line):

this looks a lot like a compter science assignment so im not gonna do it, im just gonna give you a rough idea on the algorithm i would use. assuming each row is n big.

lets take k=3, 3 can be writen as 0+3, 1+2, 2+1, 3+0, 2 can be written as 0+2, 1+1, 2+0, etc you get the idea. you could write a recusive function that breaks a number k down into a+b, that terminates at depth n then you just need to print the numbers it produces, its a bit brute force but it should work.

if you can convince me this isnt an assignment i'll provide you with some code.

Nice solution.

hko: thankyou :D especially since ive never done computer science or in fact any computer classes at all. totally self taught.

strike: i notice youve made the the assumption that k<10

It's very tricky really,

say if you've got the number 75 or so

if you've got for example an array

1,74,0,0,0

then you've got to find what exact four numbers will add up to 74

eg,

1,34,20,10,10

now you've got that what three numbers add up to 40

1,34,18,12,10

or what two numbers add up to 22

1,34,18,11,11

and so on and on, you get what I mean, there's a good few combinations and permutations in there.

[code]#include<iostream.h>
int s[20],n,mat[15][5],je=0,key=0;

void baga()
{
for(int i=1;i<=5;i++) mat[je][i]=s[i];
if(s[5]==0) key++;
}

int chk()
{ int su=0;
for(int i=1;i<=5;i++) su=su+s[i];
return(su==n);
}

void part(int ka,int n)
{
int i;
s[ka]=n;
if(chk()) { je++;baga(); }
for(i=1;i<=s[ka]-1;i++)
{ s[ka]=s[ka]-i;
part(ka+1,i);
s[ka]=s[ka]+i;
}
}

main()
{ cout<<"n=";cin>>n;
part(1,n); int j;
for(int i=1;i<=je;i++){
for(j=1;j<=5;j++) cout<<mat[i][j];
cout<<endl;
}
}[\code]

I really don't have a way to convince you that this is not an asigment. I`m from Romania and school didn't start... and I'm the second year of high-school... and they don't bother me at school with this kindda problems.

The code that I provided up will be included in a much bigger program so excuse the useless variables.
This program doesnt generate all the solution that I want:
for n=6
6 0 0 0 0
and then it jumps to the next solution
5 1 0 0 0
I need also
0 6 0 0 0
0 0 0 6 0
....
Maybe you could help me adapt the code to do that what I want
THX

umm, i have no idea what you attempting to do in that code, maybe if you used some better variable names and code tags(should have been /code not \code). please dont copy this, try and implement what i said above before you read this.

that wont come out in the order you want so you'll have to store the output instead of printing it and write a sorting function for it. also to save some stack v could be made a reference but i didnt want to confuse you with that. it could probably do with some optimisation.

<edit> changed it to a reference after all, i started thinking about large n, without the reference lower bound=4n(2+n), with reference lower bound=12n, thats quite a big difference for large n.

Well, if you don't bound the range of the elements, then there are an infinite number of solutions. I assumed that since he wanted "all the possibilities" that the numbers were bounded somehow. If they aren't bounded, then you'd have to have some sort of generator unless it was a language that used lazy evaluation (where you could just create an infinite list that holds all the solutions, essentially a generator).

At any rate you can still use the same algorithm to do it, it just won't be as easy as using n-digit numbers. However, if you don't just use n-digit numbers, you would have to first construct the list to test, and if you're going to do that then what you should do is just do the "does the sum add up to x?" test at the creation time.

my method bounds the elements(to the maximium value of an int) i just thought that a bound of 9 was quite low, and i couldnt see an easy way to modify it(but i dont know python) your algorithm is much simpler than mine and probably better at low vales of n and k but i like to solve the problem in general not just in a few cases which is why i made the comment.

Well, really mine is a general solution as well if you abstract away the 0-9 assumption. The general solution I suggest is just: create all the combinations and just iterate through them, eliminating invalid ones. Of course, for things that use the 0-9 assumption creating the range is eased by the functionality offered by some languages (like Python) in that they will create the list for you. But if you have to create the list yourself, you can still do the same thing, only it makes sense to cull up front instead of after the list is done.