LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 08-26-2003, 02:50 AM   #1
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Rep: Reputation: 30
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.
 
Old 08-26-2003, 03:55 AM   #2
Robert0380
Guru
 
Registered: Apr 2002
Location: Atlanta
Distribution: Gentoo
Posts: 1,280

Rep: Reputation: 47
you lost me with the pattern on the second part with the 5's and 1's
 
Old 08-26-2003, 07:52 AM   #3
player_2
Member
 
Registered: Aug 2003
Posts: 57

Rep: Reputation: 15
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...
 
Old 08-26-2003, 01:54 PM   #4
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
that is exacly what i mean... could you help me ?
 
Old 08-26-2003, 02:09 PM   #5
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

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

Last edited by Hko; 08-26-2003 at 02:10 PM.
 
Old 08-26-2003, 02:16 PM   #6
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
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.
 
Old 08-26-2003, 03:40 PM   #7
Strike
Member
 
Registered: Jun 2001
Location: Houston, TX, USA
Distribution: Debian
Posts: 569

Rep: Reputation: 31
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']
 
Old 08-26-2003, 04:15 PM   #8
kev82
Senior Member
 
Registered: Apr 2003
Location: Lancaster, England
Distribution: Debian Etch, OS X 10.4
Posts: 1,263

Rep: Reputation: 50
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.
 
Old 08-26-2003, 06:19 PM   #9
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

Rep: Reputation: 108Reputation: 108
Nice solution.
 
Old 08-26-2003, 06:34 PM   #10
kev82
Senior Member
 
Registered: Apr 2003
Location: Lancaster, England
Distribution: Debian Etch, OS X 10.4
Posts: 1,263

Rep: Reputation: 50
hko: thankyou 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

Last edited by kev82; 08-26-2003 at 06:46 PM.
 
Old 08-26-2003, 07:03 PM   #11
Looking_Lost
Senior Member
 
Registered: Apr 2003
Location: Eire
Distribution: Slackware 12.0, OpenSuse 10.3
Posts: 1,120

Rep: Reputation: 45
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.
 
Old 08-27-2003, 01:56 AM   #12
spank
Member
 
Registered: Aug 2003
Location: Romania
Distribution: Ubuntu 6.06
Posts: 278

Original Poster
Rep: Reputation: 30
[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
 
Old 08-27-2003, 04:26 AM   #13
kev82
Senior Member
 
Registered: Apr 2003
Location: Lancaster, England
Distribution: Debian Etch, OS X 10.4
Posts: 1,263

Rep: Reputation: 50
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.

Last edited by kev82; 08-27-2003 at 04:56 AM.
 
Old 08-27-2003, 08:03 AM   #14
Strike
Member
 
Registered: Jun 2001
Location: Houston, TX, USA
Distribution: Debian
Posts: 569

Rep: Reputation: 31
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.
 
Old 08-27-2003, 11:02 AM   #15
kev82
Senior Member
 
Registered: Apr 2003
Location: Lancaster, England
Distribution: Debian Etch, OS X 10.4
Posts: 1,263

Rep: Reputation: 50
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Best Guess on Gnome 2.8? 2Gnu Slackware 3 09-16-2004 06:06 PM
LILO problem... I guess :( jmut Slackware 8 05-05-2004 07:53 AM
problem with keyboard i guess :s Defuntu Linux - Newbie 3 03-11-2004 01:48 PM
So guess what Cichlid Linux - Networking 0 03-16-2002 05:22 PM
/etc/resolv.conf problem I guess...... cvlinux Linux - Networking 3 09-13-2001 03:46 PM


All times are GMT -5. The time now is 03:48 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration