Question 19 || Hacker Rank

Permutations of Strings || Hacker Rank

Strings are normally requested in lexicographical request. That implies they are requested by looking at their furthest left various characters. For instance, abc < abd because c < d. Likewise in light of the fact that z > yyy because z > y. In the event that one string is a careful prefix of the other it is lexicographically more modest, e.g., gh < ghij.

 

All given a variety of strings arranged in lexicographical request, print its stages in severe lexicographical request. Assuming two stages appear to be identical, just print one of them. See the 'note' beneath for a model.

 

Complete the capability next_permutation which produces the stages in the depicted request.

 

For instance, s = [ab, bc, cd]. The six changes in right request are:

               ab bc cd

               ab cd bc

               bc ab cd

               bc cd ab

               cd ab bc

               cd bc ab

 

Note: There might be at least two of similar string as components of s.

For instance,

s = [ab, bc, cd]. Just a single case of a change where all components match ought to be printed. All in all, in the event that if s[0] == s[1], then print either s[0]  s[1] or s[1]  s[0] yet not both.

 

The three component cluster having three unmistakable components has six changes as displayed previously. For this situation, there are three matching sets of stages where s[0] = ab and s[1] = ab are exchanged. We just print the three apparently novel changes:

               ab ab bc

               ab bc ab

               bc ab ab

 

Input Organization

 

The principal line of each test record contains a solitary number n, the length of the string exhibit s.

 

Every one of the following n lines contains a string s[i].

 

Requirements

 

Yield Arrangement

Print every change as a rundown of room isolated strings on a solitary line.

 

Test Info 0

   2

   ab

   cd

 

Test Result 0

   ab cd

   cd ab

 

Test Information 1

   3

   a

   bc

   bc

 

Test Result 1

   a bc bc

   bc a bc

   bc bc a

 

Clarification 1

This is like the note above. Just three of the six changes are printed to stay away from overt repetitiveness in yield.

Source Code:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int next_permutation(int n, char **s)

{

     int k = -1;

    for (int i = 0; i < n-1; i++) 

    {

        if (strcmp(s[i], s[i+1]) < 0)

            k = i;

    }

    if (k == -1) return 0; 

    int l = -1;

    for (int i = k+1; i < n; i++) 

    {

        if (strcmp(s[k], s[i]) < 0)

            l = i;

    }

    char *tmp = s[k];

    s[k] = s[l];

    s[l] = tmp;

    int i = k+1, j = n-1;

    while (i < j) 

    {

        tmp = s[i];

        s[i++] = s[j];

        s[j--] = tmp;

    }

    return 1; 

}

int main()

{

    char **s;

    int n;

    scanf("%d", &n);

    s = calloc(n, sizeof(char*));

    for (int i = 0; i < n; i++)

    {

        s[i] = calloc(11, sizeof(char));

        scanf("%s", s[i]);

    }

    do

    {

        for (int i = 0; i < n; i++)

            printf("%s%c", s[i], i == n - 1 ? '\n' : ' ');

    } while (next_permutation(n, s));

    for (int i = 0; i < n; i++)

        free(s[i]);

    free(s);

    return 0;

}

Output: