Permutation Of A String’s Characters Without Them Being In Their Initial Position

Recently, I was told to write a program which will find all the permutations of a string. But, the catch was that no character should end up in the same position as in the given string.

For Instance, if the given string is “ABC”, then the permutation should not have “A” as the first character, “B” as the second and “C” as the last one. So, the possible permutations for the input “ABC” are “BCA” and “CAB”

It might look a bit tricky. But, It’s a piece of cake if you can write a program that can find “all” permutations of the given string. You can have a look at the C program here at GeeksforGeeks.

Now, all we have to do is to write a conditional statement which will restrict the permutations where one or more characters are in their initial position. Below is the program after including one such conditional statements.

---

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

char str[] = "ABCDEF";  
char str_tmp[] = "ABCDEF";  
int str_len;

void swap(char *x, char *y) {  
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int l, int r) {  
    int i;
    if (l == r) {
        int flag = 0;
        char out[str_len];
        strcpy(out, a);
        for (i=0; i < str_len; i++) {
            if (str_tmp[i] == out[i]) {
                flag = 1;
            }
        }
        if (flag == 0) {
            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));
        }
    }
}

int main() {  
    str_len = strlen(str);
    permute(str, 0, str_len-1);
    return 0;
}

---

You can compile and execute the above program to see how well it works. Obviously, it is not an efficient way. Because, We find all the permutations and then decide whether it is valid or not. The longer the length of the string, The more time it is gonna take.