possible combination of a string

This is a discussion on possible combination of a string within the C Programming forums, part of the General Programming Boards category; Hi friends... I need to write a program in C which will print all the combinations of a string with ...

  1. #1
    Registered User
    Join Date
    Dec 2006
    Posts
    2

    possible combination of a string

    Hi friends...

    I need to write a program in C which will print all the combinations of a string with non-repeating characters. Example: “Say” will have the following: S, a,y, Sa, Sy, aS,Sy, yS, ya, aSy,Sya,ySa and so on. The string length is not known. The string will be a command line argument to the program.


    The code that i have goes below but its not giving me the desired output. the output that i m getting from this program is like

    #############OUTPUT##################
    Enter the string : say

    sya
    ysa
    yas
    ays
    asy
    say
    ##################################

    #############DESIRED OUTPUT##################
    Enter the string : say

    s
    a
    y
    sa
    sy
    as
    ys
    ay
    ya
    sya
    ysa
    yas
    ays
    asy
    say
    ###########################################

    Code:
    ###########PROGRAM################
    #include<stdio.h>
    #include<string.h>
    #include<alloc.h>
    #include<conio.h>
    
    
    void swap(char*,int);
    void gotoloop(char*,int);
    
    void main()
    {
    char *ch;
    int i,j,k,l;
    ch=(char*)malloc(20);
    //clrscr();
    printf("Enter the string\n");
    gets(ch);
    
    l=strlen(ch);
    gotoloop(ch,l);
    
    return;
    }
    
    void gotoloop(char *ch,int l)
    {
    int i,k;
    k=l;
    
    if(l<=1) 
    return;
    
    
    for(i=0;i<k;i++)
    {
    swap(ch,k);
    l--;
    gotoloop(ch,l);
    l++;
    if(k==2)
    printf("\n%s ",ch);
    }
    
    }
    
    
    void swap(char *ch,int r)
    
    {
    char c;
    int i;
    
    c=ch[r-1];
    for(i=r-1;i>0;i--)
    ch[i]=ch[i-1];
    ch[0]=c;
    }
    This is not like a normal permutation of string.

    Can anyone help me on this ASAP.

    Thanks in advance

  2. #2
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    It seems to me that you're never breaking the string down into smaller parts, therefore, whenever you print it, you're printing the whole thing.

    You would need to create new char*'s for each substring in your word (1 to 2, 1 to 3, 1 to 4, etc...) and then do the permutations on those sbustrings too.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    figure out how many of each length you have to process first
    choose(m,n)
    m! / (n!)(m-n)!
    so for your example choose(3,1) is how many single char stirngs you need. 3! = 3x2x1 = 6
    1! = 1, (3-1)! = 2
    so 6/2 = 3 single chars

    choose(3,2): 6/2 = 3 strings of length 2
    choose(3,3): 1 string of length 3

    now with that you have to get each string. from this example you will need to process 3 + 3 + 1 = 7 different strings. your current algorithm seems to be able to process the string right. You just need to process more than just "say" (1 of lenght 1) run it with "sa", "ay", "sy" (3 of length 2) and "a", "y", "s" (3 of length 1)

  4. #4
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    you maybe interested in reading this post
    Obtaining all combinations of elements...

    it describes how to get all possible sub-sets of chars from your string...
    Then you just apply your shuffle algorithm on each subset...
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ ini file reader problems
    By guitarist809 in forum C++ Programming
    Replies: 7
    Last Post: 09-04-2008, 07:02 AM
  2. Replies: 8
    Last Post: 04-25-2008, 03:45 PM
  3. Message class ** Need help befor 12am tonight**
    By TransformedBG in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2006, 11:03 PM
  4. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM
  5. creating class, and linking files
    By JCK in forum C++ Programming
    Replies: 12
    Last Post: 12-08-2002, 02:45 PM

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