how to find nth permutation of a string in c.write a c program to find nth permutation of a string. For example if given string is “1256” then all permutation of string “1256” would be

```1 2 5 6
1 2 6 5
1 5 2 6
1 5 6 2
1 6 2 5
1 6 5 2
2 1 5 6
2 1 6 5
2 5 1 6
2 5 6 1
2 6 1 5
2 6 5 1
5 1 2 6
5 1 6 2
5 2 1 6
5 2 6 1
5 6 1 2
5 6 2 1
6 1 2 5
6 1 5 2
6 2 1 5
6 2 5 1
6 5 1 2
6 5 2 1```

So if nth is 8 then nth permutation of string “1256” will be 2 1 6 5 ( i.e 7th for 0 base index ).

Let us write c program to find all permutation of given string and later on we would modify this program to find nth permutation of string.

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

int arr[4] = { 1, 2, 5, 6 };
// helper array
int parr[4];

int visited[4];

void perm(int k, int size, int nthp) {
//base case
if (k == size) {
for (int i = 0; i < size ; i++)
printf("%d", parr[i]);
printf("\n");
return;
}
for (int i = 0; i < size; i++) {
if (!visited[i]) {
visited[i] = 1;
parr[k] = arr[i];
perm(k + 1, size, nthp);
visited[i] = 0; // backtrack
}
}
}

int main() {
//reset visited
memset(visited, 0, 4);
int nthp = 8;
perm(0, 4, nthp);
return 0;
}
```

The above program will print all permutation of “1256”.

## how to find nth permutation of a string in c

From above output followings are the observation

• The length of given string “125”  is 3 and its total permutation count is 6 i.e factorial 3.
• In this way we can modify the base case of above program to find nth permutation. See below code.
```#include<stdio.h>
#include<string.h>

int arr[4] = { 1, 2, 5, 6 };
// helper array
int parr[4];

int visited[4];
int kth = 0;
void perm(int k, int size, int nthp) {
//base case
if (k == size) {
kth++;
for (int i = 0; i < size && nthp == kth; i++)
printf("%d", parr[i]);
return;
}
for (int i = 0; i < size; i++) {
if (!visited[i]) {
visited[i] = 1;
parr[k] = arr[i];
perm(k + 1, size, nthp);
visited[i] = 0; // backtrack
}
}
}

int main() {
//reset visited
memset(visited, 0, 4);
int nthp = 8;
perm(0, 4, nthp);
return 0;
}
```

Output : 2165

## optimization opportunity

The above program to find nth permutation is computing all permutation of a given string. can you think what are some optimizations require for faster execution or about reducing complexity.

`Submit your own post @ myconcept@wikistack.com`