Ad:

C++ Discussion Thread
Unsolved
Views: 9858

Nov 2nd, 2004

Producing Power set

Expand Post »

i will be given a set of any length and my program will have to produce the power set.
For example:
input: c d e

output:
empty
c
d
e
cd
de
ce
cde

total number of subsets: 2^3 = 8

I will try to write my own code, but need to to know what the algorithm would be like( an efficient one), recursive or non-recursive whatever be ur suggestion plz do explain.

Similar Threads

Power Set List from Input List in Python
Toshiba Satellite A20 in Troubleshooting Dead Machines
How Do I Wire-Up the lights/power/re-set switches on the front of my pc 2 my Mobo? in Motherboards, CPUs and RAM
Dell Inspirion 5000e randomly turning off/losing power in Troubleshooting Dead Machines

Asif_NSU

Reputation Points: 113

Solved Threads: 3

Posting Whiz

Offline

353 posts
since Apr 2004

Permalink

Nov 8th, 2004

Re: Producing Power set

Thanx for the great response

However i was working on it and prouduced this so far:
The idea is like if the binary array has elements like 0 0 1, then print the third element(corresponding entry) of the given set(char array a) which is 'c'. So if i go on like this from 0 0 0 to 1 1 1 i will get all the combinations.

C++ Syntax (Toggle Plain Text)
#include<iostream>
 
#define SIZE	3
 
using namespace std;
 
void show_subset(bool b[], char c[]);
void rec_iterate(bool b[],int n, char c[]);
 
int main()
{
	char c[]={'c','d','e'};
	bool b[SIZE]={0};
	rec_iterate(b,0,c);
 
	return 0;
}
 
void show_subset(bool b[], char c[])
{
	bool empty = true;
	for(int i = 0; i < SIZE; ++i)
		if(b[i] == 1)
		{
			empty = 0; 
			cout<<c[i];
		}		
	if(empty)
		cout<<"empty";
	cout<<"\n";
	cin.get();
}
 
void rec_iterate(bool b[],int n, char c[])
{
	for(int i = 0; i <= 1; ++i)
	{
		b[n] = i;
		if(n < SIZE -1)
			rec_iterate(b, n + 1,c);
		else
			show_subset(b, c);
	}
}
#include<iostream>

#define SIZE	3

using namespace std;

void show_subset(bool b[], char c[]);
void rec_iterate(bool b[],int n, char c[]);

int main()
{
	char c[]={'c','d','e'};
	bool b[SIZE]={0};
	rec_iterate(b,0,c);
		
	return 0;
}
	
void show_subset(bool b[], char c[])
{
	bool empty = true;
	for(int i = 0; i < SIZE; ++i)
		if(b[i] == 1)
		{
			empty = 0; 
			cout<<c[i];
		}		
	if(empty)
		cout<<"empty";
	cout<<"\n";
	cin.get();
}

void rec_iterate(bool b[],int n, char c[])
{
	for(int i = 0; i <= 1; ++i)
	{
		b[n] = i;
		if(n < SIZE -1)
			rec_iterate(b, n + 1,c);
		else
			show_subset(b, c);
	}
}

output:

C++ Syntax (Toggle Plain Text)

empty
e
d
de
c
ce
cd
cde

But i was wondering if i could produce the output like this:
empty
c
d
e
cd
de
ce
cde

i think the way i iterated the boolian array should be altered a little. A little help would be really really appreciated :-|

Asif_NSU

Reputation Points: 113

Solved Threads: 3

Posting Whiz

Offline

353 posts
since Apr 2004

Permalink

Nov 8th, 2004

Re: Producing Power set

>Thanx for the great response

Bite me. Now I'm not going to help you. But all is not lost because I found a C++ implementation of this on google that would give you a nice start. It took me about 7 seconds.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1391

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Nov 8th, 2004

Re: Producing Power set

>>Bite me. Now I'm not going to help you.
Touchy, HUH

But i was just kiddin, man! Cant even handle a joke??? Now come on man, help me out.

>> I found a C++ implementation of this on google that would give you a nice start.
I was trying to get help with "my own devised code". If i wanted to snatch the code from a website i would have already done so instead of spending my time here and not to mention the time to write my own code. But i wanted to do it myself with the help of pros like u so that i get a better understanding.

I got a tough day coming tomorrow : Midterm and quiz on Linear Algebra, quiz on Calculus and then this programming assignment. I am really getting quite restless. I apologise if i made any offense to any one bcos of that.

Asif_NSU

Reputation Points: 113

Solved Threads: 3

Posting Whiz

Offline

353 posts
since Apr 2004

Permalink

Nov 8th, 2004

Re: Producing Power set

I would try to solve the sub-problem of finding all character permutations in a string of a given length (l) that consists of n ones and l-n zeros. Then it's easy to just solve the problem first for n=1 and then increment n until it reaches l. Try that approach and see if you manage to solve your problem.

gallas

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

9 posts
since Nov 2004

Permalink

Jan 28th, 2011

-3

Re: Producing Power set

i would need a program of qbasic to calculate the power power set of a set

elemes

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

1 posts
since Jan 2011

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: array of pointers

Next Thread in C++ Forum Timeline: string arrays nedd help

DaniWeb Message

Cancel Changes

User Name
Password