Click here to Skip to main content
15,867,765 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
expected output: "abc" --> abc,acb,bca,bac,cab,cba
example outputs: when passed string s="abc" i get: cc ccc ccc


the (buggy) code is:

#include <stdio.h>
#include <cs50.h>
#include <stdlib.h>
#include <string.h>


string subS(string fullS, int s,int len);
string permut(string s ,int n);
void swap(string s,int a,int b);

int main (int argc, string argv[])
{

    if (argc!=2)
    printf("usage: ./permutation 5");

    int n = strlen(argv[1]);
    permut(argv[1],n);

    // print permutations of string s , of length n


}
  string subS(string fullS, int s,int len)

   {
      string sub = fullS;

       for(int j=0;j<len;j++)
       {
           sub[j]=fullS[s];
           s=s+1;
       }
        sub[len]='\0';
       return sub;
   }


    string permut(string s ,int n)
    {
        if (s!=NULL)
        {


            if(n==1)
                return s;
            else
            {
                string dummy_s=s;// dummy variable so as not to pass the string
                

                string sub=subS(dummy_s,1,n-1);// get the substring of s starting at s[1] and of length n-1
                
                string smaller=permut(sub,n-1);// permute the substring
                
                string final = strncat(smaller,s,1); // append the first letter of s to the permuted string.will be using it to print the permutations of
                 
                

//generating the permutations by taking s[0] and appending it to "smaller".This is done using a string "final" and swapping s[0] with its left neigbour and printing the each of these strings 
                for (int i=n-1;i>0;i--)
                {
                    printf("%s\n",final);
                    swap(final,i,i-1);
                }
                
            }
        }
        return s;

    }

    void swap(string s,int a,int b)
    {
        if (a<=b)
            return;
        else
        {
            char c= s[a];
            s[a]=s[b];
            s[b]=c;

        }
    }


What I have tried:

have tried to provide the logic of my code throug comments.Not sure what i should add here.

Posted
Updated 3-Dec-17 6:01am
v2
Comments
Richard MacCutchan 3-Dec-17 10:17am    
What is the question?
Member 13554561 3-Dec-17 10:38am    
when i run the code through debugger, i see that once I pass the dummy_s variable in the permut() function to the subS() function(to get the substring of s--the one which is to be permuted), the string s itself gets changed to what the subS() returns. Why? the whole point of sending dummy_s instead of s was so as to leave s unchanged.
Member 13554561 3-Dec-17 10:41am    
Also, is there a way to get string permutations with a function permut() which returns a string-- as i am trying here instead of a void permut() function-- which is the usual way in which such code is generally implemented? Thanks
Richard MacCutchan 3-Dec-17 10:59am    
Yes, just add a proper return statement that returns the item that you want.
Richard MacCutchan 3-Dec-17 10:58am    
I am not sure what is going on but you should not be using strncat with a std::string.

It looks to me you are overcomplicating the code.

You maight work always with the original string: the permutation function could iterate over (the received substring) characters, at each iteration (say nth) swapping the nth character
with the first one, then calling itself recursive on the resulting (smaller) substring and eventually restoring the received content by swapping again.
 
Share this answer
 
As far as I understand it, your code is completely wrong.
First of all you need to study the algorithm until you understand it.
Take a sheet of paper and practice, think that your only tool to get all permutation is the swap function, think mechanical. Advice: Practice with at least 4 letters to expose repetitive patterns.
Recursion permutations - C++ Forum[^]

It may gelp to learn one or more analyze methods, E.W. Djikstra top-Down method is a good start.
https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design[^]
https://en.wikipedia.org/wiki/Structured_programming[^]
https://en.wikipedia.org/wiki/Edsger_W._Dijkstra[^]
https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF[^]
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900