LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (http://www.linuxquestions.org/questions/programming-9/)
-   -   I guess a simple backtracking problem (http://www.linuxquestions.org/questions/programming-9/i-guess-a-simple-backtracking-problem-85785/)

spank 08-26-2003 02:50 AM

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.

Robert0380 08-26-2003 03:55 AM

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

player_2 08-26-2003 07:52 AM

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...

spank 08-26-2003 01:54 PM

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

Hko 08-26-2003 02:09 PM

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

spank 08-26-2003 02:16 PM

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.

Strike 08-26-2003 03:40 PM

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):

Code:

>>> [str(x).zfill(5) for x in range(100000) if sum(map(int,list(str(x)))) == 6]
['00006', '00015', '00024', '00033', '00042', '00051', '00060', '00105', '00114', '00123', '00132', '00141', '00150',
 '00204', '00213', '00222', '00231', '00240', '00303', '00312', '00321', '00330', '00402', '00411', '00420', '00501',
 '00510', '00600', '01005', '01014', '01023', '01032', '01041', '01050', '01104', '01113', '01122', '01131', '01140',
 '01203', '01212', '01221', '01230', '01302', '01311', '01320', '01401', '01410', '01500', '02004', '02013', '02022',
 '02031', '02040', '02103', '02112', '02121', '02130', '02202', '02211', '02220', '02301', '02310', '02400', '03003',
 '03012', '03021', '03030', '03102', '03111', '03120', '03201', '03210', '03300', '04002', '04011', '04020', '04101',
 '04110', '04200', '05001', '05010', '05100', '06000', '10005', '10014', '10023', '10032', '10041', '10050', '10104',
 '10113', '10122', '10131', '10140', '10203', '10212', '10221', '10230', '10302', '10311', '10320', '10401', '10410',
 '10500', '11004', '11013', '11022', '11031', '11040', '11103', '11112', '11121', '11130', '11202', '11211', '11220',
 '11301', '11310', '11400', '12003', '12012', '12021', '12030', '12102', '12111', '12120', '12201', '12210', '12300',
 '13002', '13011', '13020', '13101', '13110', '13200', '14001', '14010', '14100', '15000', '20004', '20013', '20022',
 '20031', '20040', '20103', '20112', '20121', '20130', '20202', '20211', '20220', '20301', '20310', '20400', '21003',
 '21012', '21021', '21030', '21102', '21111', '21120', '21201', '21210', '21300', '22002', '22011', '22020', '22101',
 '22110', '22200', '23001', '23010', '23100', '24000', '30003', '30012', '30021', '30030', '30102', '30111', '30120',
 '30201', '30210', '30300', '31002', '31011', '31020', '31101', '31110', '31200', '32001', '32010', '32100', '33000',
 '40002', '40011', '40020', '40101', '40110', '40200', '41001', '41010', '41100', '42000', '50001', '50010', '50100',
 '51000', '60000']


kev82 08-26-2003 04:15 PM

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.

Hko 08-26-2003 06:19 PM

Nice solution.

kev82 08-26-2003 06:34 PM

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

Looking_Lost 08-26-2003 07:03 PM

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.

spank 08-27-2003 01:56 AM

[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

kev82 08-27-2003 04:26 AM

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.

Code:

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int n, k;

void recur(int num, int level, vector<int> &v)
{
    if(level == n) {
        if(accumulate(v.begin(), v.end(), 0) != k) return;

        for(int i=0; i<v.size(); i++) cout << v[i];
        cout << endl;
        return;
    }

    for(int i=0; i<=num; i++) {
        v[level]=num-i;
        recur(i, level+1, v);
    }
}

int main()
{
    n=5, k=6;
    vector<int> v(n);

    recur(k, 0, v);
    return 0;
}

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.

Strike 08-27-2003 08:03 AM

Quote:

Originally posted by kev82
strike: i notice youve made the the assumption that k<10
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.

kev82 08-27-2003 11:02 AM

Quote:

Well, if you don't bound the range of the elements
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.


All times are GMT -5. The time now is 09:45 AM.