Permuting the words of a string

10th October, 2010

Given a string, how can you permute all words of the string? The question was asked here.

Given below is the working code. Algorithmic steps can be understood from the comments.

// Prints all the words in the string array

void printTheArray(char *array[], int size)

{

    static int count;

    int index;

    printf("%d ", count);

    for(index = 0; index < size; index++)

    {

        printf("%s ", array[index]);

    }

    count++;

    printf("\n");

}

// swpping integers is easy, swapping strings nothing but swapping their base

inline

void swapStringPointers (char *stringsVector[], int i, int j)

{

    char *base;

    base = stringsVector[i];

    stringsVector[i] = stringsVector[j];

    stringsVector[j] = base;

}

// Actual permutation algorithm (recursive)

inline

void permuteWords (char *stringsVector[], int vectorSize, int processedIndex)

{

    int currentIndex;

    if (processedIndex == vectorSize)

    {

        // print the vector

        printTheArray(stringsVector, vectorSize);

    }

    else

    {

        for (currentIndex = processedIndex; currentIndex < vectorSize; currentIndex++)

        {

            // No need to swap the same element

            if(currentIndex != processedIndex)

                swapStringPointers (stringsVector, processedIndex, currentIndex);

            // Recursively permute the smaller instances

            permuteWords (stringsVector, vectorSize, processedIndex + 1);

            // No need to swap the same element

            if(currentIndex != processedIndex)

                swapStringPointers (stringsVector, processedIndex, currentIndex);

        }

    }

}

int main ()

{

    // Just add one more string if you want to test

    char *strings[] = {"SARI", "GAMA", "PADA", "NISA"};

    int size = sizeof(strings)/sizeof(strings[0]);

    // Prints original array

    printTheArray(strings, size);

    printf("\n");

    // Permutes all words in the string

    permuteWords (strings, size, 0);

    return 0;

}