Can anyone suggest me the necessary changes for my code?

Question

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. Below are the permutations of string ABC. ABC ACB BAC BCA CBA CAB

The following code of all possible string permutation is coded using backtracking , but its not working , anyone please suggest necessary changes.

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\n", 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);
    return 0;
    }

Answer 1

This is a classic case of OBOB (Of By One Bug).

The index of the last character of a n-length string is n-1, so when looping over all indices inside your string, the loop shouldn't be for (i = l; i <= r; i++), but for (i = l; i < r; i++).

Calling swap() with an index that is too big, creates weird effects, such as making your string shorter.

This is the permute() function after the change:

void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i < r; i++)  // corrected indices
      {
         swap((a+l), (a+i));
         permute(a, l+1, r);
         swap((a+l), (a+i)); //backtrack
       }
   }
 }

It should work now.