Problem...


 Topic: Problem...
Users reading this topic: There are no members reading this topic.
  Posted on November 26, 2013 16:08
uzumakhi_naruto
Rank: member

Forum Rank:
Genin

Posts: 133
Joined on:
June 5, 2009
#1
Hey guys ! I need your sincerely help on info.
Program used : Borland C++
Class : #11
Metode used : backtraking
Problem : Generate, using backtracking, all parts of a set with n elements. Two or more sets create a partition of a set if they don't have common elements and the union of all sets is itself set the main elements.
eg: n=3 and {1, 2, 3}
=> | {1}, {2}, {3} | | {1, 2}, {3} | | {1, 3}, {2} | | {1}, {2, 3} |

Thanx a lot if somebody will share a good program :push
152kt35.jpg
▬◘ My free shop ₪₪₪ Best Player-Card ₪₪₪ My free gfx ◘▬
© ♫ b.gifalin_nr01 my alt acc :cool - My Youtube Channel - :amused b.gif
  Posted on November 26, 2013 16:17
pradeepmittal2
Rank: member

Forum Rank:
Sannin

Posts: 3989
Joined on:
May 2, 2011
#2
This works in C

#include <iostream>
#include <vector>

using namespace std;

vector<int> people;
vector<int> combination;

void pretty_print(const vector<int>& v) {
static int count = 0;
cout << "combination no " << (++count) << ": [ ";
for (int i = 0; i < v.size(); ++i) { cout << v << " "; }
cout << "] " << endl;
}

void go(int offset, int k) {
if (k == 0) {
pretty_print(combination);
return;
}
for (int i = offset; i <= people.size() - k; ++i) {
combination.push_back(people);
go(i+1, k-1);
combination.pop_back();
}
}

int main() {
int n = 5, k = 3;

for (int i = 0; i < n; ++i) { people.push_back(i+1); }
go(0, k);

return 0;
}


And here's output for N = 5, K = 3:

combination no 1: [ 1 2 3 ]
combination no 2: [ 1 2 4 ]
combination no 3: [ 1 2 5 ]
combination no 4: [ 1 3 4 ]
combination no 5: [ 1 3 5 ]
combination no 6: [ 1 4 5 ]
combination no 7: [ 2 3 4 ]
combination no 8: [ 2 3 5 ]
combination no 9: [ 2 4 5 ]
combination no 10: [ 3 4 5 ]

Edit:I hope the same code will help you to make changes as per c++
  Posted on November 26, 2013 16:22
uzumakhi_naruto
Rank: member

Forum Rank:
Genin

Posts: 133
Joined on:
June 5, 2009
#3
pradeepmittal2 wrote:
This works in C

#include <iostream>
#include <vector>

using namespace std;

vector<int> people;
vector<int> combination;

void pretty_print(const vector<int>& v) {
static int count = 0;
cout << "combination no " << (++count) << ": [ ";
for (int i = 0; i < v.size(); ++i) { cout << v << " "; }
cout << "] " << endl;
}

void go(int offset, int k) {
if (k == 0) {
pretty_print(combination);
return;
}
for (int i = offset; i <= people.size() - k; ++i) {
combination.push_back(people);
go(i+1, k-1);
combination.pop_back();
}
}

int main() {
int n = 5, k = 3;

for (int i = 0; i < n; ++i) { people.push_back(i+1); }
go(0, k);

return 0;
}


And here's output for N = 5, K = 3:

combination no 1: [ 1 2 3 ]
combination no 2: [ 1 2 4 ]
combination no 3: [ 1 2 5 ]
combination no 4: [ 1 3 4 ]
combination no 5: [ 1 3 5 ]
combination no 6: [ 1 4 5 ]
combination no 7: [ 2 3 4 ]
combination no 8: [ 2 3 5 ]
combination no 9: [ 2 4 5 ]
combination no 10: [ 3 4 5 ]

Edit:I hope the same code will help you to make changes as per c++

"k" don't exist , is just n. And thx for your work but i don't study C and i don't know all that structures in your problem
152kt35.jpg
▬◘ My free shop ₪₪₪ Best Player-Card ₪₪₪ My free gfx ◘▬
© ♫ b.gifalin_nr01 my alt acc :cool - My Youtube Channel - :amused b.gif
  Posted on November 26, 2013 16:26
uzumakhi_naruto
Rank: member

Forum Rank:
Genin

Posts: 133
Joined on:
June 5, 2009
#4
Again example :
For n=3 and set wrote : {1,2,3}
The program will show next solutions :
{1}, {2}, {3}
{1, 2}, {3}
{1, 3}, {2}
{1}, {2, 3}

- sorry for doublepost -
152kt35.jpg
▬◘ My free shop ₪₪₪ Best Player-Card ₪₪₪ My free gfx ◘▬
© ♫ b.gifalin_nr01 my alt acc :cool - My Youtube Channel - :amused b.gif
  Posted on November 26, 2013 16:27
pradeepmittal2
Rank: member

Forum Rank:
Sannin

Posts: 3989
Joined on:
May 2, 2011
#5
int main() {
int n = 5, k = 3;

for (int i = 0; i < n; ++i) { people.push_back(i+1); }
go(0, k);

return 0;
}
void go(int offset, int k) {
if (k == 0) {
pretty_print(combination);
return;
}
for (int i = offset; i <= people.size() - k; ++i) {
combination.push_back(people);
go(i+1, k-1);
combination.pop_back();
}
}

I bolded wherever i used "k"
btw this code is giving static value to N and K if u want to give a value from user then u can use scanf and take inputs from user in N and K

int main() {
int n = 5, k = 3; // remove this line
scanf("%d%d",&n,&k); //Use this to take input
for (int i = 0; i < n; ++i) { people.push_back(i+1); }
go(0, k);

return 0;
}
  Posted on November 26, 2013 16:32
uzumakhi_naruto
Rank: member

Forum Rank:
Genin

Posts: 133
Joined on:
June 5, 2009
#6
Edit : Ohh , now i understand all. One of my friends explained me all details on your problem and he didn't knowed to resolve this too.
Well , thx a lot bro , you really helped me ; tomorrow my prof need to mark me and i will be
prepared. Thx again !!!
152kt35.jpg
▬◘ My free shop ₪₪₪ Best Player-Card ₪₪₪ My free gfx ◘▬
© ♫ b.gifalin_nr01 my alt acc :cool - My Youtube Channel - :amused b.gif
  Posted on November 26, 2013 17:05
pradeepmittal2
Rank: member

Forum Rank:
Sannin

Posts: 3989
Joined on:
May 2, 2011
#7
uzumakhi_naruto wrote:
Edit : Ohh , now i understand all. One of my friends explained me all details on your problem and he didn't knowed to resolve this too.
Well , thx a lot bro , you really helped me ; tomorrow my prof need to mark me and i will be
prepared. Thx again !!!

Did i miss something?
i was preparing for my job tomorrow.......I am happy to hear that you are prepared for your professor ^_^

Edit: By the way ,C++ is not my genre.I am an iOS developer so feel free to ask me any questions regarding that if you have :amused