C – String Permutations using swapping

hello there,

i was pretty bored in this week end so i started to think let me do some useful thing, and i ended up doing some sort of encryption algorithm pretty weak for the time being, but im still working on it. i will share it once im done with it, but what i will share is how to get any string permutations which i needed for the algorithm using swapping and  recursion.

I believe the Time Complexity is O(n*n) which is not bad,

so first we will do the swapping function  to swap 2 characters, this function will be called inside permutate function.

void swap (char *fc, char *sc)
{
    char temp;
    temp = *fc;
    *fc = *sc;
    *sc = temp;

}

then do the permutation function

void permutate(char *string,int start, int end)
{
    if (start == end)
    {
        printf("%sn",string);
    }
    else
    {
        for (int i = start;i <= end; i++)
        {
            swap(&(*(string+start)), &(*(string+i)));
            permutate(&*string, start+1, end);
            swap(&(*(string+start)), &(*(string+i)));
        }
    }
}

if you are reading the string from STDIN then reading the string from STDIN in an efficient way

char *content;
    char c = 0;
    int i = 0;
    while(c != 'n')
    {
        c = fgetc(stdin);
        content = (char*)realloc(content, i+1);
        *(content + i) = c;
        i++;
    }

then call the permutate function. Kindly note if you sorted the string before doing permutation you will drop a lot of duplicates from the output so it depends on what do you want.

Posted in Programming and tagged , , , , , , , , , , , . Bookmark the permalink. RSS feed for this post. Leave a trackback.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

Swedish Greys - a WordPress theme from Nordic Themepark.