subset algorithm

This is a discussion on subset algorithm within the C Programming forums, part of the General Programming Boards category; Write a recursive function (without using for,while,do while)that fills the given character array with all possible given-size subsets of characters ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    12

    subset algorithm

    Write a recursive function (without using for,while,do while)that fills the given character
    array with all possible given-size subsets of characters in
    given word, separated by commas. You need to put a
    trailing \0 in the character array. You can assume that
    the word is at most 10 in length.
    void subsets(char word[], int sz, char arr []);
    The function then can be used as follows:
    char w[] = "abcd";
    char r[200];
    subsets(w, 2, r );
    puts(r );

    the output must be
    ab,ac,ad,bc,bd,cd
    and for
    subsets(w, 3, r );
    the output must be
    abc,abd,acd,bcd
    to be printed on the console. Pay attention to the order
    of the words—those need to be in the same order as one
    produced by the supplied executable!
    Here, you can use functions from <string.h>.
    can any one help me to find any algorithm or code to due with this question ??
    tanq

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Nope, but if you post your code, we'll try to help you reach a solution yourself.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    12
    good idea,this is the code ,its not done,i didnt even compile it yet i am working on it but thats it pretty much (by the way i cant use static variable either!!!)
    Code:
    #include <stdio.h>
    
    void subsets(char word[], int sz, char arr [])
    {
    	int arrc=0,flag=11,i=0,d=0;
    	char dep[10];
    	subsetf2(word,sz,arr,i,d,dep,flag,arrc);
    	
    }
    subsetf2(char word[],int r,char arr,int i,int d,char dep[],int flag,int arrc)
    {
    	flag=subsetfunc1(word,r,arr,i,d,dep,flag,arrc);
    	if(flag==strlen(word));
    	subsetf2(word,r,arr,++i,d,dep,flag,arrc);
    
    
    }
    
    subsetfunc1(char word[],int r,char arr,int i,int d,char dep[],int flag,int arrc)
    {
    	if(strlen(dep)==r) 
    	{
    		
    		dep[d]='\0';
    		flag=d-1;
    		arrc=arrint(arr,dep,arrc);
    	     return (flag);
    	}
    	if(i==flag) subsetfunc1(word,r,arr,++i,d,dep,flag,arrc);
    	dep[d]=word[i];
    	subsetfunc1(word,r,arr,++i,++d,dep,flag,arrc);
    }
    int arrint(char arr[],char dep[],int j,int arrc)
    {
    	if(dep[j]=='\0') 
    	{
    	arr[arrc]=',';
    	return(arrc);
    	}
    	arr[arrc]=dep[j];
       return arrint(arr,dep,++j,++arrc);
    }
    
    
    
    
    
    	   
    	   
    	   void main()
    {
    	char w[] = "abcd";
    char r[200];
    subsets(w, 2, r);
    }
    Last edited by calc; 06-24-2009 at 10:47 AM.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    That seems a bit too much.

    Have you ever watched an odometer work? Do you think you can adapt that idea for your purposes?

  5. #5
    Registered User
    Join Date
    Jun 2009
    Posts
    12
    ya...it works but i dont know how to make the code...my idea is pretty much like odometer but its hard to develop!!

  6. #6
    Registered User NeonBlack's Avatar
    Join Date
    Nov 2007
    Posts
    435
    First of all, never write that much non-trivial code without compiling. (I did something very similar to this about a year ago and it took me several hours to write and debug)
    Without examining your code too closely, it looks like you have the right general idea, although I think your solution is too complicated.
    I would reconsider the "odometer" idea since for input (abc, 2), aa, ba, bb, cb, etc are invalid.
    Do you have a systematic method of generating these subsets by hand? You might want to explain it here. Putting it in writing might clarify your thought process.
    I copied it from the last program in which I passed a parameter, which would have been pre-1989 I guess. - esbo

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21