We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. C
  3. Functions
  4. Permutations of Strings
  5. Discussions

Permutations of Strings

Sort by

recency

|

134 Discussions

|

  • sezzaldiin0
     + 0 comments
     // Step 1: Find the largest index k such that s[k] < s[k + 1]
    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; // No next permutation
    }

    // Step 2: Find the largest index l greater than k such that s[k] < s[l]
    int l = -1;
    for (int i = k + 1; i < n; i++) {
        if (strcmp(s[k], s[i]) < 0) {
            l = i;
        }
    }

    // Step 3: Swap the value of s[k] with that of s[l]
    char *temp = s[k];
    s[k] = s[l];
    s[l] = temp;

    // Step 4: Reverse the sequence from s[k + 1] to s[n - 1]
    for (int i = k + 1, j = n - 1; i < j; i++, j--) {
        temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    return 1; // Next permutation exists

  • a2hnaak
     + 1 comment

    Refer here : https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

    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;
    }
    // printf("k = %d",k);

    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;
    }
    // printf("\nl = %d",l);
    
    
    if(l!=-1)
    {
        char* temp = s[k];
        s[k] = s[l];
        s[l] = temp;
    }
        
    //Reverse the sequence from a[k + 1] up to and including the final element a[n].
    int start=k+1;
    int end=n-1;
    while (start < end) {
      char*  temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
    
        
    
    
    return 1;
}

  • tpaolini
     + 1 comment

    So here is the logic in plain English:

    1. Find the rightmost string that is lexographically smaller than its next string. If none is found, then there is no next permutation.
    2. Find the rightmost string that is lexographically smaller than the string from Step 1.
    3. Swap with each other the strings from Step 1 and Step 2.
    4. Reverse the order of all strings that come after the original position of the string from Step 1.

  • 22RH1A0538
     + 0 comments

    include

    include

    include

    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;

    }

  • rejin_gunasekar1
     + 0 comments
    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char **a, char **b){
    char *temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(char **s, int start, int end){
    while(start < end){
        swap(&s[start], &s[end]);
        start++;
        end--;
    }
}

int next_permutation(int n, char **s)
{
    int i = n - 2;
    if(i < 0){
        return 0;
    }
    while(i >= 0 && strcmp(s[i], s[i + 1]) >= 0){
        i--;
    }
    if(i < 0){
        return 0;
    }
    int j = n - 1;
    while(strcmp(s[i], s[j]) >= 0){
        j--;
    }
    swap(&s[i], &s[j]);
    reverse(s, i + 1, n - 1);
    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;
}