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

|

137 Discussions

|

  • 23641a05h5
     + 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; // 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

    }

    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; }

  • zero006607578
     + 0 comments

    Tried to make is as simple as possible

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

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

  • mcsilvio
     + 1 comment

    This is a horrible question.

    • awatatani6402
       + 0 comments

      I agree lol

  • sezzaldiin0
     + 1 comment
     // 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

    • ke_kaiwen168
       + 1 comment

      Thanks but if size of array is large..I think better to start at the end:

      for (int i = n-2; i >=0; i--) {
    if (strcmp(s[i], s[i + 1]) < 0) {
        k = i;
        break;
    }
}

      • sezzaldiin0
         + 0 comments

        it still worked

  • 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;
}

    • GrigorG1
       + 0 comments

      Thank you for the wikipedia link!!!

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in