Alexey Sharov - 6 months ago 91

C Question

I want to print all permutation of string in lexicographic order. I write this code:

`void permute(char *a, int i, int n) {`

if (i == (n-1)) printf("\"%s\"\n", a);

else {

for (int j = i; j < n; j++) {

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

permute(a, i+1, n);

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

}

}

}

And I have for example string

`abc`

`"abc" "abc"`

"acb" "acb"

"bac" "bac"

"bca" "bca"

"cab" <

"cba" "cba"

> "cab"

Can someone help me with this? I saw some algorithms, but they look difficult. I think I can save all generated strings in array and then sort this array, but I cannot write this (I'm beginner in C).

Answer

There's a pretty straightforward description of an algorithm (plus implementation) at geeksforgeeks:

Given a string, print all permutations of it in sorted order. For example, if the input string is “ABC”, then output should be “ABC, ACB, BAC, BCA, CAB, CBA”.

We have discussed a program to print all permutations in this post, but here we must print the permutations in increasing order.

Following are the steps to print the permutations lexicographic-ally

Sort the given string in non-decreasing order and print it. The first permutation is always the string sorted in non-decreasing order.

Start generating next higher permutation. Do it until next higher permutation is not possible. If we reach a permutation where all characters are sorted in non-increasing order, then that permutation is the last permutation.

Steps to generate the next higher permutation:

1. Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.

Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’.

Swap the two characters found in above 2 steps.

Sort the substring (in non-decreasing order) after the original index of ‘first character’.

I've re-implemented it below:

```
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void swap(char* left, char* right)
{
char temp = *left;
*left = *right;
*right = temp;
}
int compare (const void * a, const void * b)
{
return ( *(char*)a - *(char*)b );
}
void PrintSortedPermutations(char* inStr)
{
// Re-implementation of algorithm described here:
// http://www.geeksforgeeks.org/lexicographic-permutations-of-string/
int strSize = strlen(inStr);
// 0. Ensure input container is sorted
qsort(inStr, strSize, sizeof(char), compare);
int largerPermFound = 1;
do{
// 1. Print next permutation
printf("%s\n", inStr);
// 2. Find rightmost char that is smaller than char to its right
int i;
for (i = strSize - 2; i >= 0 && inStr[i] >= inStr[i+1]; --i){}
// if we couldn't find one, we're finished, else we can swap somewhere
if (i > -1)
{
// 3 find character at index j such that
// inStr[j] = min(inStr[k]) && inStr[k] > inStr[i] for all k > i
int j = i+1;
int k;
for(k=j;k<strSize && inStr[k];++k)
{
if (inStr[k] > inStr[i] && inStr[k] < inStr[j])
j = k;
}
// 3. Swap chars at i and j
swap(&inStr[i], &inStr[j]);
// 4. Sort string to the right of i
qsort(inStr+i+1, strSize-i-1, sizeof(char), compare);
}
else
{
largerPermFound = 0;
}
}while(largerPermFound);
}
int main(void) {
char str[] = "abc";
PrintSortedPermutations(str);
return 0;
}
```

abc

acb

bac

bca

cab

cba

`std::next_permutation`

from the `<algorithm>`

library will do this for you, just make sure you sort your container first:

## Return value

true if the function could rearrange the object as a lexicographicaly greater permutation. Otherwise, the function returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).

For example:

```
std::string myStr = "abc";
std::stable_sort(std::begin(myStr), std::end(myStr));
do {
for(auto&& element : myStr)
std::cout << element << " ";
std::cout << std::endl;
} while (std::next_permutation(std::begin(myStr), std::end(myStr)));
```

Output:

a b c

a c b

b a c

b c a

c a b

c b a