Thread: I need help!!!

  1. #1
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154

    Question I need help!!!

    Code:
    Hello everybody.
    
    I have a problem and i need help.
    
    Here is a set {a,b,c,d,e,f,.......,w,x,y,z}
    I want to make a program to read a number  and to print all possible subsets from 'a' to digit that the chosen number shows.For example:
    
    %Please give number.
    Given number is 2 and these are the subsets of {a,b} :
    {}
    {a}
    {b}
    {a,b}
    
    %Please give number.
    Given number is 4 and these are the subsets of {a,b,c,d} :
    {}
    {a}
    {b}
    {a,b}
    {c}
    {a,c}
    {b,c}
    {a,b,c}
    {d}
    {a,d}
    {b,d}
    {c,d}
    {a,b,d}
    {a,c,d}
    {b,c,d}
    {a,b,c,d}
    
    Thanks

  2. #2
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154
    I try this but nothing
    Code:
    #include<stdio.h>
    int main(void){
        int A[26],B[26],i,j,k,l,max,o,z,x,c,v;
        
        for(i=0;i<26;i++){B[i]='a'+i;}
        printf("Give num");
        scanf("%d",&max);
        for(i=0;i<max;i++){
                           printf("%c\n",B[i]);
                           for(j=0;j<i;j++){
                                            A[j]=0;
                                            }
                           for(j=0;j<i;j++){
                                            A[j]=B[j];
                                            }
                           for(j=0;j<=i-1;j++){
                                              
                                              for(k=j;k<=i-1;k++){
                                                                 printf("%c",A[k]);
                                                                 for(o=k;o<=i-1;o++){
                                                                                     printf("%c",A[o]);
                                                                 for(z=o;z<=i-1;z++){
                                                                                     printf("%c",A[z]);
                                                                 }
                                                                 }
                                                                 printf("%c\n",B[i]);
                                                                 A[k]=B[k+1];
                                              
                                                                 }
                                                                 printf("%c\n",B[i]);
                                                                 A[o]=B[o+1];                   
                                              }                  
                           }
    getchar();                       
    getchar();
    }

  3. #3
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    for n = 4 we can represent each possible subset of the set
    Code:
    {a,b,c,d}
    in the following way:
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    1001
    1010
    1011
    1100
    1101
    1110
    1111

    where 1 indicates that the corresponding item should be present in the subset and 0 that it should not be present

    as easy to see the above values can be simply generated by the binary representation of the numbers from 0 to 15

    so what I suggest
    take number n
    build number m thats binary representation has n 1: 0000111...1
    and make a loop from 0 to m
    for each i get the binary representation of the number and build the subset
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  4. #4
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154
    Thanks
    1.Each time, i want to print the string and not the number
    2.I can not understand absolute what you mean
    Code:
    take number n
    build number m thats binary representation has n 1: 0000111...1
    and make a loop from 0 to m
    for each i get the binary representation of the number and build the subset

  5. #5
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    For example
    6 = 110 in binary representation

    so we get 0110 sequence

    taking 2nd and 3rd mamber of the /a,b,c,d/ set we get (b,c) subset

    3 = 11
    0011 -> (c,d)

    10 = 1010 -> (a,c)
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Imagine something like this:

    You have a small array with 2 char's in it: a, & b.

    Which could be shown as just binary numbers 0 - 3. The first zero on the left representing Array[1], and the second zero representing Array[2]
    Arrays begin in C with the subscript zero, but we're just not using it for this example.

    2, 1
    ^^
    00 - Empty set. Zero Array[2]'s and Zero Array[1]'s.
    01 - Zero Array[2]'s, One Array[1], (no b's, one a)
    10 - One Array[2], Zero Array[1]'s (one b, no a's)
    11 - One Array[2], and One Array[1] (one b, one a)

    Hope that helps.

    Adak
    Last edited by Adak; 01-14-2007 at 07:47 AM.

  7. #7
    The Artful Lurker Deckard's Avatar
    Join Date
    Jan 2002
    Posts
    633
    Here's a rough draft that goes backwards and always displays a fixed length field, but it should help:
    Code:
    void printSubsets( int range )
    {
       int index;
       int field; /* assuming 26-bits or more */
       char output[27] = { 0 };
    
       /* quick input validation */
       if ( range < 1 || range > 26 )
          return;
    
       for ( field = (1 << range) - 1; field; field-- )
       {
          /* Build the output */
          for ( index = 0; index < range; index++ )
          {
             if ( (field & (1 << index)) != 0 )
                output[index] = 'a' + index;
             else
                output[index] = ' ';
          }
    
          /* Display the output */
          printf( "%s\n", output );
       }
    }
    Keep in mind that using all twenty-six letters in the alphabet will give you 67,108,864 subsets. There are several good discussions on bit operations in this forum. Naturally, I'm partial to this one.
    Jason Deckard

  8. #8
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    for bitwise operations better to use unsigned int
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  9. #9
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154
    Thanks Everybody!!!
    Code:
    2, 1
    ^^
    00 - Empty set. Zero Array[2]'s and Zero Array[1]'s. 
    01 - Zero Array[2]'s, One Array[1], (no b's, one a)
    10 - One Array[2], Zero Array[1]'s (one b, no a's)
    11 - One Array[2], and One Array[1] (one b, one a)
    What do you mean Zero Array[2]'s and One Array[1], (no b's, one a)
    Do we use two types of Arrays?
    Can you show me what included in Array?


    Code:
    Here's a rough draft that goes backwards and always displays a fixed length field, but it should help:
    Thanks a lot Deckard it works.

  10. #10
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Quote Originally Posted by ch4
    What do you mean Zero Array[2]'s and One Array[1], (no b's, one a)
    Zero - in the bit-representation was 0
    Zero Array[i] - don't take element i of the Array

    One - in the bit represantation was 1 on this place
    One Array[i] - take element i into the subset from the Array
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  11. #11
    The Artful Lurker Deckard's Avatar
    Join Date
    Jan 2002
    Posts
    633
    Quote Originally Posted by vart
    for bitwise operations better to use unsigned int
    The sign bit isn't a factor in this situation.

    However, as a general rule (and to benefit those who may not know why), sure: use unsigned integers when using integers as bit fields. Why? Because the high order bit in signed integers is reserved to indicate if the number is positive or negative.
    Last edited by Deckard; 01-14-2007 at 02:25 PM. Reason: Spelling correction
    Jason Deckard

  12. #12
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154
    Thank Everyone
    Mixing all your ideas i made this
    Code:
    #include<stdio.h>
    int power(int,int);
    int main(void){
        int A[27],i,j,max,k,n;
        scanf("%d",&max);
        for(i=0;i<max;i++){
                           A[i]=0;
                           }
         printf("{ }\n");
         n=power(2,max)-1;             
        for(i=0;i<n;i++){
                         A[max-1]=A[max-1]+1;
                         for(j=max;j>=0;j--){
                                             if(A[j]==2){
                                                         A[j]=0;
                                                         A[j-1]=A[j-1]+1;
                                                         }
                                             }
                         putchar('{');                    
                         for(j=0;j<max;j++){                                        
                                            if(A[j]==1){
                                                        k='a'+j;
                                                        printf("%c,",k);
                                                        }
                                            }
                         printf("\b}\n");
                         }    
    }
    
    
    int power(int base, int n)
    { int p;
      for (p=1 ; n > 0 ; n--)                /* base^n equals to */
        p *= base;         /* base * base * ... * base (n times) */
      return p;                                 /* Return result */
    }

Popular pages Recent additions subscribe to a feed