a recursive algorithm problem
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12

Thread: a recursive algorithm problem

  1. #1
    Join Date
    May 2004
    Posts
    52

    a recursive algorithm problem

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

  2. #2
    Join Date
    Apr 2003
    Location
    Los Angeles area
    Posts
    776
    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].

  3. #3
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    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.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  4. #4
    Join Date
    Dec 2001
    Location
    Greece, Athens
    Posts
    1,015
    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.
    Theodore
    Personal Web Page (some audio segmentation tools): www.di.uoa.gr/~tyiannak

  5. #5
    Join Date
    Dec 2001
    Location
    Greece, Athens
    Posts
    1,015
    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:
    Code:
    #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 "{_,_,_,_}"
    Theodore
    Personal Web Page (some audio segmentation tools): www.di.uoa.gr/~tyiannak

  6. #6
    Join Date
    Dec 2001
    Location
    Greece, Athens
    Posts
    1,015
    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):

    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
    Theodore
    Personal Web Page (some audio segmentation tools): www.di.uoa.gr/~tyiannak

  7. #7
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588
    The same idea in C++, by using sets:
    Code:
    #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 << "&#091;";
        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 << "&#093;" << 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;
    }
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  8. #8
    Join Date
    May 2004
    Posts
    52

    thank you so much

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

  9. #9
    Join Date
    Apr 2003
    Location
    Los Angeles area
    Posts
    776
    I think this was supposed to be someones homework but ok....

    Code:
    #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.

  10. #10
    Join Date
    Jun 2004
    Posts
    17
    heres another possibility.

    Code:
    (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....

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


    a bit wordy, i admit.
    :-)

  11. #11
    Join Date
    Dec 2001
    Location
    Greece, Athens
    Posts
    1,015
    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
    Theodore
    Personal Web Page (some audio segmentation tools): www.di.uoa.gr/~tyiannak

  12. #12
    Join Date
    Nov 2004
    Location
    Houghton, Michigan
    Posts
    3

    Re: a recursive algorithm problem

    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

    Code:
    //------------------
    // 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

    Code:
    //-----------------
    // 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?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)