string permutation
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 14 of 14

Thread: string permutation

  1. #1
    Join Date
    Jul 2007
    Posts
    8

    Unhappy string permutation

    Hi,

    Greetings to all,

    I am new to this forum , may I ask could if you please give the link to the code for permutation in strings treated as char arrays that is already in this forum . I tried ask.com to reach here for the code. Actually I am unable to develop the correct logic working behind this problem.

    I kow that if "joy" is input then output would be
    according to index positions :

    joy
    jyo
    ojy
    oyj
    yoj
    yjo

    Code:
    #include<iostream.h>
    #include<conio.h>  // these headers need to be modified as per new rules in c++
    #include<string.h>
    int main()
    {
       char a[100];
       char per[100];
       cout<<" word";
       cin.get(a,100);
        stcpy(per,a);
      
    int l=strlen(per);
    for(int x=0;x<l;x++)
     for(int y=0;y<l;y++)
     {
       if(x!=y)
      cout<<per[y];
      }
      cout<<per[x]<<endl;
    }
    getchar();
    return 0;
    }
    I use turbo C++ for compiling

    Help needed in getting hold of different ( index )values of x so that I could swap them up to print 6 combinations instead of 3 .

    if you just print per[x]in if loop you will get
    oy// 1,2
    jy //0,2
    jo //0,1
    The current output is
    oyj
    jyo
    joy

    and my output requires
    012
    021
    102
    120
    210
    201

    With lots of hope,
    hinduengg

  2. #2
    Join Date
    Dec 2004
    Location
    Poland
    Posts
    1,165

    Re: string permutation

    Do you need to create whole permutation thing by yourself? Or maybe you can use std::next_permutation?

    Cheers
    B+!
    'There is no cat' - A. Einstein

    Use &#91;code] [/code] tags!

    Did YOU share your photo with us at CG Members photo gallery ?

  3. #3
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,623

    Re: string permutation

    Does Turbo C++ support the standard C++ library ? If
    so, there is already a routine which does permutations.
    (to get all permutations, the input string must be sorted).
    See below for example:

    Code:
    #include <iostream>
    #include <algorithm>
    #include <string.h>
    
    int main()
    {
        char per[100];
    
        strcpy(per,"joy");
      
        int l=strlen(per);
    
        std::sort(per,per+l);
    
        std::cout << per << "\n";
    
        while (std::next_permutation(per,per+l))
        {
            std::cout << per << "\n";
        }
    
        return 0;
    }
    Output :

    joy
    jyo
    ojy
    oyj
    yjo
    yoj

  4. #4
    Join Date
    Jul 2007
    Posts
    8

    Re: string permutation

    Thank you for the reply. Actually I need to do this with char arrays only that it is the instruction of my teacher . Do you think my logic or code is flawed . Well thats why the output it produces is not correct. I would be obliged if you would devote some of your precious time to glance through my code and find flaws in it.

    I am basically unable to obtain the successive values of x in the if loop.
    If i get the individuals I could do swapping b/w the two values like

    joy

    y=0 so x =1 and x=2 at which if is true so I want to swap these index values .
    Should I use break to get hold the values but I am unable to fit the statement in the correct manner.


    Code:
    char a[100];
    char temp;
    
    temp=a[1];
    a[1]=a[2];
    a[2]=temp;

  5. #5
    Join Date
    Nov 2003
    Posts
    1,405

    Re: string permutation

    Quote Originally Posted by hinduengg
    Thank you for the reply. Actually I need to do this with char arrays only that it is the instruction of my teacher . Do you think my logic or code is flawed . Well thats why the output it produces is not correct. I would be obliged if you would devote some of your precious time to glance through my code and find flaws in it.
    If the output is wrong the code is wrong. Simple as that.

    If the purpose of the task is to generate permutations then you shouldn't bother too much about the actual C++ code at first. First you should develop a strategy for generating permutations. This is not an easy task though. Are you sure you haven't been adviced on this?

  6. #6
    Join Date
    Aug 2005
    Location
    Netherlands, The
    Posts
    2,184

    Re: string permutation

    this may be easier than u think.

    1. iterate swap from end to begin
    2. iterate swap from begin to end
    do this X times which is strlen*Y times, (havent been able to figure out Y)

    swap= swap the characters next to eachother

    im not sure if this works

  7. #7
    Join Date
    Nov 2003
    Posts
    1,405

    Re: string permutation

    Quote Originally Posted by Mitsukai
    im not sure if this works
    Then why the heck are you posting it?

    Do you post just about any crap just to post something?

  8. #8
    Join Date
    Aug 2005
    Location
    Netherlands, The
    Posts
    2,184

    Re: string permutation

    from GCC STL

    Code:
      /**
       *  @brief  Permute range into the next "dictionary" ordering.
       *  @param  first  Start of range.
       *  @param  last   End of range.
       *  @return  False if wrapped to first permutation, true otherwise.
       *
       *  Treats all permutations of the range as a set of "dictionary" sorted
       *  sequences.  Permutes the current sequence into the next one of this set.
       *  Returns true if there are more sequences to generate.  If the sequence
       *  is the largest of the set, the smallest is generated and false returned.
      */
      template<typename _BidirectionalIterator>
        bool
        next_permutation(_BidirectionalIterator __first,
    		     _BidirectionalIterator __last)
        {
          // concept requirements
          __glibcxx_function_requires(_BidirectionalIteratorConcept<
    				  _BidirectionalIterator>)
          __glibcxx_function_requires(_LessThanComparableConcept<
    	    typename iterator_traits<_BidirectionalIterator>::value_type>)
          __glibcxx_requires_valid_range(__first, __last);
    
          if (__first == __last)
    	return false;
          _BidirectionalIterator __i = __first;
          ++__i;
          if (__i == __last)
    	return false;
          __i = __last;
          --__i;
    
          for(;;)
    	{
    	  _BidirectionalIterator __ii = __i;
    	  --__i;
    	  if (*__i < *__ii)
    	    {
    	      _BidirectionalIterator __j = __last;
    	      while (!(*__i < *--__j))
    		{}
    	      std::iter_swap(__i, __j);
    	      std::reverse(__ii, __last);
    	      return true;
    	    }
    	  if (__i == __first)
    	    {
    	      std::reverse(__first, __last);
    	      return false;
    	    }
    	}
        }
    which is something like this

    Code:
    bool next_permutation(char* first, char* last)
    {
      char* i = last - 1;
      if(first >= i) return false;
      while(true)
      {
        char* ii = i;
        if(*--i < *ii)
        {
          char* j = last;
          while(!(*i < *--j));
          *i ^= *j;
          *j ^= *i;
          *i ^= *j;
          //std::reverse(ii, last);
          return true;
        }
    
        if(i == first)
        {
          //std::reverse(first, last);
          return false;
        }
      }
    }
    Last edited by Mitsukai; July 20th, 2007 at 12:03 AM.

  9. #9
    Join Date
    Oct 2000
    Location
    London, England
    Posts
    4,773

    Re: string permutation

    if you have to implement it yourself, the simplest way is to use recursion.
    Code:
    void recurse_output_permutations
      ( 
           const std::string & remaining, 
           const std::string  & used, 
           std::ostream & output 
      )
    {
       if ( remaining.empty() )
       {
            output << used << '\n';
            return;
       }
       for( int i=0; i < remaining.size(), ++i ) // ok write it better if you like
       { 
            char ch = remaining[i];
            std::string next_remaining( remaining );
            next_remaining.erase( i ); 
            std::string next_used( used );
            next_used.push_back( char );
            recurse_output_permutations( next_remaining, next_used );
      }
    }
            
    void output_permutations( const std::string & text )
    {
       recurse_output_permutations( text, "", std::cout );
    }

  10. #10
    Join Date
    Jul 2007
    Posts
    8

    Re: string permutation

    Thank you so much , although the functions used in your codes are very good but my problem is that I need to manually play with indexes of x to get my output.

    Those big functions are not required , not to hurt you its just that I have not been taught this until now.

    We have to use simple loops and simple C++ string (char array) functions.

    Could you throw light on what is recursive programming?
    So that when it is taught in class it will be easy for me to grasp.

    This question has troubled a lot since 3 weeks and I do not think that I am near to solution. Please pertain to my code please.

    Thanking you,
    hinduengg

  11. #11
    Join Date
    Oct 2000
    Location
    London, England
    Posts
    4,773

    Re: string permutation

    written in C it might look like this:

    Code:
    #include <stdio.h>
    
    void swap( char * first, char * second )
    {
       if ( first != second )
       {
          char temp = *second;
          *second = *first;
          *first = temp;
       }
    }
    
    void recurse_output_permutations
      ( 
           char * text,
           int length,
           int partition
      )
    {
       if ( partition == length )
       {
           puts( text );
           return;
       }
       char * end = text + length;
       char * part = text + partition;
    
       for ( char * ch = part; ch != end; ++ch )
       {
           swap( ch, part );
           recurse_output_permutations( text, length, partition + 1 );
           swap( ch, part ); 
       }
    }
            
    void output_permutations( char * text, int len )
    {
       recurse_output_permutations( text, len, 0 );
    }
    
    int main()
    {
       char text[] = "stop";
       output_permutations( text, 4 );
    }
    Note this works without making any allocations but if you want to pass in a const char * then your function must make a copy of the string to make it writable.



    If you are allowed to use some C++ then you might want to use vector<char> to do this rather than new[] or malloc/strdup (which you would have to use in C).

    Output:

    stop
    stpo
    sotp
    sopt
    spot
    spto
    tsop
    tspo
    tosp
    tops
    tpos
    tpso
    otsp
    otps
    ostp
    ospt
    opst
    opts
    ptos
    ptso
    pots
    post
    psot
    psto
    Last edited by NMTop40; July 20th, 2007 at 09:58 AM.

  12. #12
    Join Date
    Jul 2007
    Posts
    8

    Smile Re: string permutation

    THANK YOU NM240 ,your solution is awesome , but please could you throw light on what these lines do in the code:


    Code:
      char * end = text + length;
       char * part = text + partition;
    My code has to be in C++ but after you explain in C I would get the logic to implement it in C++.

    I would be highly obliged.

    Thanking you,
    hinduengg
    Last edited by hinduengg; July 25th, 2007 at 09:16 AM.

  13. #13
    Join Date
    Jun 2007
    Location
    Vercelli, Italy
    Posts
    87

    Re: string permutation

    Could you throw light on what is recursive programming?
    So that when it is taught in class it will be easy for me to grasp.
    May I suggest you to read this article? Its main topic is the merge sort algorithm, but the beginning of the article discusses recursion.
    I owe Paul McKenzie a pizza.

    I am no expert; but they say I can make concepts easy to understand. That's why newbies questions are mine!!! XD

  14. #14
    Join Date
    Jul 2007
    Posts
    8

    Exclamation Re: string permutation

    Thank you Sk# for the nice article and I am sorry to NM top 40 for I misspelled your name. You are one of the gurus of this forums. Sorry.
    But my recent question still lingers on . Please try to solve it

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 is a CodeGuru survey question.


Featured


HTML5 Development Center