a recursive algorithm problem

[forfan]

the task is to output all the sub set of the original set.
sth like this: when original set is [a,b,c],
then output goes to: [],[a],[b],[c],[a,b],[a,c],[b,c],[a,b,c].

the solution is restricted to recursive algorithm.

can anyone help me?

maybe this is a stupid question
:-<

[Joe Nellis]

Not a stupid question. It's not an inherently trivial problem but I have seen it before, variants, from comp sci classes. There are probably many ways to solve it but here is some insight into the problem as it relates to a possible program implementation.

You are given the full set always so there is no missing information. You are going from [a,b,c] to [_],[a],[b],[c],[a,b],[a,c],[b,c],[a,b,c]. I will represent the empty set by using an underscore character '_' . Now consider that the empty set, which is always part of the set, can be written instead of just [_] but also like [_,_,_]. And that [a,b] is really [a,b,_], and [a,c] is potentially [a,_,c].

[Yves M]

You can start the recursion with the following observation:

Any subset either contains the first element or it doesn't.

Now you can call this recursively with the second, third etc. element and you will get all subsets.

[yiannakop]

Originally posted by Yves M
You can start the recursion with the following observation:

Any subset either contains the first element or it doesn't.

Now you can call this recursively with the second, third etc. element and you will get all subsets.
But, how can you implement the fact that a subset either contains the 1st element or it doesn't?
Regards,
Theodore.

[yiannakop]

Ok, I think I implemented an C program based on what Yves said. It is simple and has global variables and generally it is bad programming, but I think it works fine:

#include <stdio.h>

char Global[100];
int GlobalN;

void subset(char *array,int N)
{
if (N>0)
{
char *newA = (char*)malloc(sizeof(char)*(N-1));
char *newB = (char*)malloc(sizeof(char)*(N-1));
memcpy(newA,array+1,N-1);
Global[N-1] = '_';
subset(newA,N-1);
memcpy(newB,array+1,N-1);
newB[N-1] = '_';
Global[N-1] = array[0];
subset(newB,N-1);

}
else
{
int i;
for (i=0;i<GlobalN;i++)
printf("%c",Global[i]);
printf("\n");
return;
}
}

main()
{
int N = 4;
char *a = (char*)malloc(sizeof(char)*N);
a[0] = 'a';
a[1] = 'b';
a[2] = 'c';
a[3] = 'd';
GlobalN = N;
subset(a,N);

return 0;
}


PS: the program also writes "_" characters. So the empty subset is written as "{_,_,_,_}"

[yiannakop]

The idea of the program is the same as when writting combinations of binary digits:
000
001
010
011
100
101
110
111

The algorithm for writing such a sequence in a recursive way is like this (pseudo-code):


function write_binary(N)
{
IF (N!=0)
a[N] = 0;
write_binary(N-1);
a[N] = 1;
write_binary(N-1);
ELSE
print_array(a);
}

, where a is a global array

Regards,
Theodore

[Yves M]

The same idea in C++, by using sets:

#include <iostream>
#include <vector>
#include <set>
#include <string>

template <typename T>
void output_subsets(std::set<T> *all_values, std::set<T> *selected_values)
{
if (all_values->empty()) {
// No more remaining values to be treated
// So we print out what we have selected
std::cout << "[";
for (std::set<T>::iterator it = selected_values->begin(); it != selected_values->end(); ++it) {
// If we are not on the first value, print a comma
if (it != selected_values->begin()) {
std::cout << ", ";
}
std::cout << *it;
}
std::cout << "]" << std::endl;
} else {
// Take the first element of all_values
std::set<T>::iterator it = all_values->begin();
T tmp = *it;
all_values->erase(it);

// Call recursively without the first element added
output_subsets(all_values, selected_values);
// Call recursively with the first element added
selected_values->insert(tmp);
output_subsets(all_values, selected_values);

// restore the sets
selected_values->erase(tmp);
all_values->insert(tmp);
}
}

int main()
{
// For characters
std::set<char> all_cval, sel_cval;
for (char c = 'a'; c < 'e'; ++c) {
all_cval.insert(c);
}
output_subsets(&all_cval, &sel_cval);

// For strings
std::set<std::string> all_sval, sel_sval;
all_sval.insert("Hello");
all_sval.insert("World");
all_sval.insert("And");
all_sval.insert("The");
all_sval.insert("Rest");
output_subsets(&all_sval, &sel_sval);

return 0;
}

[forfan]

Yeah, that is an interesting problem.
I've learned a lot from your reply threads.

[Joe Nellis]

I think this was supposed to be someones homework but ok....


#include <string>
#include <iostream>

using namespace std;

/* set count
abc = 000
ab = 001
a c = 010
a = 011
bc = 100
b = 101
c = 110
= 111
*/
void recursivefunction(string set, int count)
{
int i =0;
bool firstelement = true;
string temp;

while(i < set.size()){
if(!(count>>i & 1)){ // test first bit
if(!firstelement) // if not the first element in subset, produce a comma
temp = set.substr(set.size()-1-i,1) + ","+temp;
else{
temp = set.substr(set.size()-1-i,1);
firstelement = false;
}
}
++i;
}
if(count) // if not the first subset, produce a comma
cout << ",[" << temp << "]";
else
cout << "[" << temp << "]";
++count;
if(count% (1<<set.size()) ==0) // bailout condition, 2^setsize is number of subsets
return;
recursivefunction(set,count);
}

int main(int argc, char* argv[])
{
string set;
cout << "enter the characters of the set:" << endl;
cin >> set;
recursivefunction(set,0);
cout << endl;
return 0;
}

The order is not outputted from lowest number of elements to most number of elements in a subset like the original poster has his examples. For that a temporary storage container that you could sort by subset string size and first element, could be used until outputting at the end of the program or in the bailout condition.

[jono]

heres another possibility.


(defun power-set (set)
(if (null set) '(())
(let ((rest (power-set (cdr set))))
(append
(mapcar #'(lambda (subset)
(cons (car set) subset)) rest) rest]



for example....


>> (power-set '(a b c))
((A B C) (A B) (A C) (A) (B C) (B) (C) NIL)




a bit wordy, i admit.
:-)

[yiannakop]

I remembered that I've done this once in prolog, but it was some years ago and I probably have that homework at home. If interested, tell me. Generally prolog is the best language for recursive algorithms and with list operations.
Regards,
Theodore

[njpaul]

Even though this topic is by now nearly 6 months old I feel it is best to add a new solution to a similar problem. In my programming class we had to make a set library, and one of the functions was to overload the ~ operator and return a set pointer to an array of sets, namely the power set. The reason it does this is because our set only holds integers, thus adding a set as an item to a set would be a better solution but is not allowed. Here's what I came up with. Note this is an iterative solution


//------------------
// Returns the power set
//------------------
Set * Set::operator ~ (void)
{
// gets the new size of 2^n and adds one to
// account for the element that stores the size
int nPowSize = (2 << (this->m_nSize-1)) + 1;

Set *Pow = new Set[nPowSize];

// store size in the first element of the first
// set in the array
Set cSet;
cSet.Add(nPowSize);
Pow[0] = cSet;

// go through the size of the power set
// and add the element in position j to the
// current set if its bit is 1
for(int i=0; i < nPowSize; ++i)
{
for(int j=0; j < this->m_nSize; ++j)
{
if(i & (1<<j))
{
// i+1 accounts for the Pow[0] being dedicated the the
// size of the set
Pow[i+1].Add(this->GetElement(j));
}
}
}

return Pow;
} // operator ~



Then to print out the power set we overload the << operator



//-----------------
// Formats the cout to print
// the set pointer
//-----------------
ostream& operator << (ostream &out, Set *pRhs)
{
int nElem = 0;
int nSize = pRhs[0].GetElement(0);
out << "{";
if(nSize > 0)
{
for(int i=1; i < (nSize-1); i++)
{
out << pRhs[i] << ", ";
}
out << pRhs[nSize-1];
}
out << "}";
return out;
} // operator <<



By the way, this isn't exactly most optimized version of the solution. There were rumors around that you could do a modified merge to get it in a faster time. Does anyone have that algorithm?