Rewrite the for loop for the random permutation generator of

Rewrite the for loop for the random permutation generator of Section 2.2 as a recursive function. (from Cliffton Shaffer\'s Data Structures and Algorithm Analysis in Java 3e)

Solution

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.

Given a string, print all permutations of a given string.

Input:

The first line of input contains an integer T denoting the number of test cases.
Each test case contains a single string in capital letter.

Output:

Print all permutations of a given string with single space and all permutations should be in lexicographically increasing order.

Constraints:

1 T 10
1 size of string 5

Example:

Input:
2
ABC

ABSG

Output:
ABC ACB BAC BCA CAB CBA

ABGS ABSG AGBS AGSB ASBG ASGB BAGS BASG BGAS BGSA BSAG BSGA GABS GASB GBAS GBSA GSAB GSBA SABG SAGB SBAG SBGA SGAB SGBA

here is the example code

// C program to print all permutations with duplicates allowed

#include <stdio.h>

#include <string.h>

/* Function to swap values at two pointers */

void swap(char *x, char *y)

{

    char temp;

    temp = *x;

    *x = *y;

    *y = temp;

}

/* Function to print permutations of string

   This function takes three parameters:

   1. String

   2. Starting index of the string

   3. Ending index of the string. */

void permute(char *a, int l, int r)

{

   int i;

   if (l == r)

     printf(\"%s\ \", a);

   else

   {

       for (i = l; i <= r; i++)

       {

          swap((a+l), (a+i));

          permute(a, l+1, r);

          swap((a+l), (a+i)); //backtrack

       }

   }

}

/* Driver program to test above functions */

int main()

{

    char str[] = \"ABC\";

    int n = strlen(str);

    permute(str, 0, n-1);

    return 0;

}

// C program to print all permutations with duplicates allowed #include <stdio.h> #include <string.h> /* Function to swap values at two pointers */ void swap(char *x, char *y) {     char temp;     temp = *x;     *x = *y;     *y = temp; } /* Function to print permutations of string    This function takes three parameters:    1. String    2. Starting index of the string    3. Ending index of the string. */ void permute(char *a, int l, int r) {    int i;    if (l == r)      printf(\"%s\ \", a);    else    {        for (i = l; i <= r; i++)        {           swap((a+l), (a+i));           permute(a, l+1, r);           swap((a+l), (a+i)); //backtrack        }    } } /* Driver program to test above functions */ int main() {     char str[] = \"ABC\";     int n = strlen(str);     permute(str, 0, n-1);     return 0; }